La résolution de l'Entier à Dos

J'ai une nouvelle dynamique de programmation et ont essayé de l'entier à dos problème ici au SPOJ (http://www.spoj.pl/problems/KNAPSACK/) . Cependant, pour le cas de test ma solution n'est pas de donner la bonne sortie. Je serais reconnaissant si vous pouviez proposer si à la suite de la mise en œuvre par moi est correct. Veuillez noter que la variable back est de revenir en arrière, à propos de laquelle je ne suis pas sûr de la façon de faire. J'espère avoir votre aide dans la mise en œuvre de la mandature. 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 la bonne entrée/de sortie en cas de test:

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


Output:
13

Cependant, le résultat que j'obtiens est 17.

"Toutefois, pour le cas de test ma solution n'est pas de donner de bons résultats." L'entrée de qui? La sortie considérez-vous corriger? et quelle sortie vous avez réellement obtenir?
Non, il n'est pas.

OriginalL'auteur hytriutucx | 2012-06-14

  1. 8

    C'est une version du sac à Dos problème connu comme le sac à dos 0-1.

    Vous faites quelques erreurs stupides dans votre code.

    Commencer avec le premier entier en entrée est le poids et la deuxième est la valeur. Pendant que vous prenez la première valeur et la deuxième de poids. En outre, vous prenez n+1 valeurs d'entrée de 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 0-1. Lire ce http://en.wikipedia.org/wiki/Knapsack_problem .

    Je suis venu avec cet algorithme, et j'ai soumis et acceptés. 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 tableaux de simplement utiliser des vecteurs

    vector <int> My_array(n);
    Dans le code que vous simplement retourner M[n-1][C] après le remplissage de la matrice. Est-il nécessaire de parcourir la dernière ligne de la matrice de trouver le plus grand M[n-1][j] et le retour de cette plus grande valeur que discuté sur le lien suivant: people.csail.mit.edu/bdean/6.046/dp

    OriginalL'auteur sukunrt

  2. 3

    Il existe une version du problème de sac-à-dos bien documentés à 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 entrée exemple ne semble pas à charger avec le code que tu fournis (il est à la recherche d'une paire supplémentaire que prévu en raison de la <= N). J'attends que la boucle doit être < N, pour obtenir 0..n-1 éléments.

    De fixation que j'obtiens un résultat de 134516145 imprimés, ce qui est absurde.

    OriginalL'auteur Godeke