Rozwiązywanie Integer Knapsack

Question

Jestem nowy w programowaniu dynamicznym i wypróbowałem problem z plecakiem całkowitym tutaj na SPOJ (http://www.spoj.pl/problems/KNAPSACK/). Jednak dla podanych przypadków testowych moje rozwiązanie nie podaje poprawnego wyniku. Byłbym wdzięczny, gdybyś mógł zasugerować, czy poniższa implementacja jest prawidłowa. Zwróć uwagę, że zmienna back służy do cofania, o której nie wiem, jak to zrobić. Mam nadzieję, że pomogę ci również w implementacji backtrackingu. Dzięki.

#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 

using namespace std; 

int knapsack(int value[], int weight[], int n, int C, 
     vector <int>&back) 
{ 
    int *M = new int[C + 1]; 
    int k; 
    int i, j, tmp, pos; 
    for (i = 1; i <= C; i++) { 
     M[i] = M[i - 1]; 
     pos = i - 1; 
     for (j = 0; j < n; j++) { 
      k = i - weight[j]; 
      if (k >= 0) 
       tmp = M[k] + value[j]; 
      if (tmp > M[i]) { 
       M[i] = tmp; 
      } 
     } 
     back.push_back(pos); 
    } 
    int ans = M[C]; 
    delete[]M; 
    return ans; 
} 


int main() 
{ 
    int C, N; 
    cin >> C >> N; 
    int* value = new int[N+1]; 
    int* weight = new int[N+1]; 
    for (int i = 0; i <= N; i++) { 
     cin>>value[i]>>weight[i]; 
    } 
    vector <int>back(N, 0); 
    cout<<knapsack(value,weight,N,C,back)<<endl; 
    return 0; 
} 

Oto poprawne przypadki testowe wejścia/wyjścia:

Input: 
4 5 
1 8 
2 4 
3 0 
2 5 
2 3 


Output: 
13 

jednak wyjście, że jestem coraz to 17.

Answer 1

Jest to wersja problemu z plecakiem nazywanego plecakiem 0-1.

Robisz kilka głupich błędów w swoim kodzie.

Na początek pierwsza liczba całkowita na wejściu to waga, a druga to wartość. Podczas gdy bierzesz pierwszą wartość, a drugą wagę. Ponadto przyjmujesz wartości n + 1 jako wejście 0 do N włącznie.

Teraz w swoim algorytmie rozważasz możliwość wykonania dowolnej liczby kopii przedmiotów, nie jest to prawdą, że jest to plecak 0-1. Przeczytaj to http://en.wikipedia.org/wiki/Knapsack_problem.

Wpadłem na ten algorytm, a ja przesłałem i zostałem zaakceptowany. To powinno działać dobrze.

int M[2000][2000]; 
int knapsack(int value[], int weight[], int C, int n) 
{  
    for(int i = 1; i <= C; i++){ 
    for(int j = 0; j <n; j++){ 
     if(j > 0){ 
     M[j][i] = M[j-1][i]; 
     if (weight[j] <= i) 
      M[j][i] = max(M[j][i], M[j-1][i-weight[j]]+value[j]); 
     } 
     else{ 
     M[j][i] = 0; 
     if(weight[j] <= i) 
      M[j][i] = max(M[j][i], value[j]); 
     } 
    } 
    // cout << M[i][n-1] << endl; 
    }   
    return M[n-1][C]; 
} 

int main() 
{ 
    int C, N; 
    cin >> C >> N; 
    // cout << C << endl; 
    int* value = new int[N+1]; 
    int* weight = new int[N+1]; 
    for (int i = 0; i < N; i++) { 
     cin>>weight[i]>>value[i]; 
    } 
    // vector <int>back(N, 0); 
    cout<<knapsack(value,weight,C,N)<<endl; 
    return 0; 
} 

BTW nie dynamicznie przydzielać tablice po prostu używać wektorów

vector <int> My_array(n); 

Answer 2

Istnieje wersja problemu z plecakiem udokumentowana w https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p w języku Python.

EDYCJA: Nieważne, pominąłem część, w której wejście pierwszej linii definiuje C i N. To powiedziawszy, twój przykład wejściowy nie wydaje się ładować z podanym kodem (szuka jeszcze jednej pary, niż byłoby to oczekiwano ze względu na < = N). Spodziewam się, że pętla powinna być < N, aby uzyskać 0..n-1 jako elementy.

Naprawiono, że otrzymałem wydruk w postaci 134516145, co jest bezsensowne.