Risoluzione dello zaino intero

Question

Ho iniziato a programmare in modo dinamico e ho provato il problema dello zaino intero qui a SPOJ (http://www.spoj.pl/problems/KNAPSACK/). Tuttavia, per i casi di test indicati, la mia soluzione non fornisce l'output corretto. Ti sarei grato se potessi suggerire se la seguente implementazione da parte mia è corretta. Si noti che la variabile back è per il backtracking, di cui non sono sicuro come fare. Spero di avere il tuo aiuto per implementare anche il backtracking. Grazie.

#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; 
} 

Qui ci sono i casi di test di ingresso/uscita corrette:

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


Output: 
13 

Tuttavia, l'output che sto ottenendo è 17.

Answer 1

Questa è una versione del problema dello zaino noto come lo zaino 0-1.

Stai facendo degli stupidi errori nel codice.

Per iniziare con il primo intero in input è il peso e il secondo è il valore. Mentre tu stai prendendo prima come valore e secondo come peso. Inoltre stai prendendo n + 1 valori come input da 0 a N inclusi.

Ora nel tuo algoritmo, stai considerando che puoi prendere un numero qualsiasi di copie degli articoli, questo non è vero questo è uno zaino da 0 a 1. Leggi questo http://en.wikipedia.org/wiki/Knapsack_problem.

Mi sono inventato questo algoritmo e l'ho presentato e accettato. Quindi questo dovrebbe funzionare bene.

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 non allocare dinamicamente gli array è sufficiente utilizzare vettori

vector <int> My_array(n); 

Answer 2

C'è una versione del problema dello zaino documentata bene in https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p in Python.

EDIT: Nevermind, ho saltato la parte in cui l'ingresso prima riga definisce C e N. Detto questo, il tuo esempio di input non sembra caricare con il codice che hai fornito (che è alla ricerca di un paio di più di quanto sarebbe previsto a causa dello < = N). Mi aspetto che il ciclo dovrebbe essere < N, per ottenere 0..n-1 come elementi.

Risolvere il problema relativo al risultato della stampa 134516145, che è priva di senso.