Pourquoi est-ce DP solution à la 0/1 à Dos Problème, de ne pas donner la bonne sortie avec GCC?

#include<stdio.h>
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void knapsack(int m,int n,int w[],int p[])
{
int v[10][10],x[10],i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(j==0||i==0)
v[i][j]=0;
if(j-w[i]<0)
v[i][j]=v[i-1][j];
else
v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
}
}
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
printf("%d\t",v[i][j]);
printf("\n");
}
printf("THE OPTIMAL SOLUTION IS:%d",v[n][m]);
for(i=1;i<=n;i++)
x[i]=0;
i=n;
j=m;
while(i>0 && j>0)
{
if(v[i][j]!=v[i-1][j])
{
x[i]=1;
j=j-w[i];
}
i--;
}
printf("THE OPTIMAL SET OF WEIGHTS IS:");
for(i=1;i<=n;i++)
if(x[i]==1)
printf("%d\t",i);
printf("\n");
}
int main()
{
int w[10],p[10],i,m,n;
printf("ENTER THE NUMBER OF ITEMS:");
scanf("%d",&n);
printf("ENTER THE WEIGHTS OF THE ITEMS:");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("ENTER THE PROFITS OF THE ITEMS:");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
printf("ENTER THE CAPACITY OF KNAPSACK:");
scanf("%d",&m);
knapsack(m,n,w,p);
return 0;
}

EXEMPLE DE SORTIE:

chaitanya@chaitanya-laptop:~/Desktop/My prog$ ./a.out
ENTER THE NUMBER OF ITEMS:5
ENTER THE WEIGHTS OF THE ITEMS:3
2
1
2
3
ENTER THE PROFITS OF THE ITEMS:2
3
2
3
2
ENTER THE CAPACITY OF KNAPSACK: 8
0   -72 -1080992920 -72 0   1   -1080993280 0   13403040    
0   -72 -1080992920 2   0   1   -70 2   13403040    
0   -72 3   2   0   5   3   4   13403040    
0   2   3   5   4   5   7   5   13403040    
0   2   3   5   6   8   7   8   13403040    
0   2   3   5   6   8   7   8   13403040    
THE OPTIMAL SOLUTION IS:13403040
THE OPTIMAL SET OF WEIGHTS IS:

Remarque: Le même programme produit un légitime de sortie pour la même entrée lors de la compilation dans le "Turbo C" compilateur.

Donc ce qui m'amène à croire que je ne suis pas adhérant à C de normes. Est-ce vrai?

Essayez d'utiliser un débogueur comme gdb et de compiler votre programme avec -Wall -g

OriginalL'auteur Chaitanya Nettem | 2011-11-20

  1. 10

    Lorsque vous initialisez w vous utilisez 1-l'indexation en fonction de:

    for(i=1;i<=n;i++)
scanf("%d",&w[i]);

    Mais lorsque vous y accédez, vous êtes à l'aide de 0 basée sur l'indexation.

    for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(j==0||i==0)
v[i][j]=0;
if(j-w[i]<0)   //This line accesses w[0] when i is 0. Missing an else?
v[i][j]=v[i-1][j];
else
v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
}
}

    En C les tableaux de 0 basée sur l'indexation. Modifiez votre code pour utiliser 0 basée sur l'indexation de manière cohérente.

    Aussi, vous devez vérifier la valeur de retour de scanf invalide entrée de donner des résultats étranges au lieu d'une erreur.

    for (i=0; i < n; i++) {
if (scanf("%d", &w[i]) != 1) {
return EXIT_FAILURE; //Handle the error appropriately.
}
}
    je sais que les tableaux sont 0 indexé mais dans ce cas, je ne suis pas accès à w[0] n'importe où.
    oui dans un scénario idéal, je devrais vérifier pour la rupture possible causant des conditions, mais clairement, pour la donnée d'entrée ni de points dont vous parlez sont à l'origine d'une erreur.
    Oui, vous l'êtes. À l'intérieur de la boucle interne qui assigne à v[i][j], une première fois.
    ok...désolé un peu de changement peut être pour l'indice de problème...vous avez raison.
    Voir ma réponse mis à jour. J'ai posté un extrait du code où vous avez accès à w[0].

    OriginalL'auteur Mark Byers

  2. -1

    peut-être avec le même code.. y compris les < limites.h > travail.. juste faire 0e indexé élément à l'infini) par (nom du tableau)[0]=-INT_MAX.

    Je ne vois pas comment cela pourrait résoudre OP problème. Si cela peut aider, veuillez préciser comment.

    OriginalL'auteur Khushal