Résoudre le sac à dos Integer

Question

Je suis un débutant dans la programmation dynamique et j'ai essayé le problème du sac à dos entier ici à SPOJ (http://www.spoj.pl/problems/KNAPSACK/). Cependant, pour les cas de test donnés, ma solution ne donne pas la bonne sortie. Je vous serais reconnaissant si vous pouviez suggérer si la mise en œuvre suivante par moi est correcte. S'il vous plaît noter que la variable back est pour le retour en arrière, sur lequel je ne suis pas sûr de savoir comment faire. J'espère avoir votre aide dans la mise en œuvre du backtracking aussi. Merci.

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

Voici les cas de test d'entrée/sortie correcte:

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


Output: 
13 

Cependant, la sortie que je reçois est 17.

Answer 1

Il s'agit d'une version du problème Knapsack connu sous le nom de sac à dos 0-1.

Vous faites des erreurs stupides dans votre code. Pour commencer, le premier entier en entrée est le poids et le second est la valeur. Alors que vous prenez d'abord comme valeur et seconde comme poids. De plus, vous prenez n + 1 comme entrée 0 à N inclus.

Maintenant dans votre algorithme, vous considérez que vous pouvez prendre n'importe quel nombre de copies des éléments, ce n'est pas vrai c'est un sac à dos de 0-1. Lisez ceci http://en.wikipedia.org/wiki/Knapsack_problem.

Je suis venu avec cet algorithme et j'ai soumis et j'ai été accepté. Donc, cela devrait fonctionner correctement.

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 ne pas allouer dynamiquement des réseaux utilisent simplement des vecteurs

vector <int> My_array(n); 

Answer 2

Il existe une version du problème de sac à dos bien documentée à https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p en Python.

EDIT: Nevermind, j'ai sauté la partie où la première ligne d'entrée définit C et N. Cela dit, votre exemple de saisie ne semble pas charger avec le code que vous avez fourni (il cherche une paire de plus que serait attendu en raison du < = N). Je m'attends à ce que cette boucle soit < N, pour obtenir 0..n-1 comme éléments. Fixation que je reçois un résultat de 134516145 imprimé, ce qui est absurde.