为什么这个0/1背包问题的DP解决方案在使用GCC时不能给出正确的输出？

Question

为什么这个0/1背包问题的DP解决方案在使用GCC时不能给出正确的输出？

7

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

样例输出：

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:

注意: 当使用“Turbo C”编译器编译相同的输入时，同一程序会产生合法的输出。

所以这让我相信我没有遵守C标准。是这样吗？

- Chaitanya Nettem

1

尝试使用像gdb这样的调试器，并使用-Wall -g编译您的程序。 - Basile Starynkevitch

2个回答

-1

可能使用相同的代码.. 包括 < limits.h > 将会工作.. 只需将第0个索引元素设置为负无穷大，即 (数组名称)[0]=-INT_MAX。

- Khushal

我不明白这如何解决 OP 的问题。如果它有帮助，请详细说明如何解决。 - absoluteAquarian

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

当你初始化 w 时，你正在使用基于1的索引：

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

但是当你访问它时，你使用的是基于0的索引。

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]);
    }
}

C语言中数组使用0-based索引。请将代码更改为始终使用0-based索引。

另外，您应该检查scanf的返回值，否则无效的输入会导致奇怪的结果而不是错误。

for (i=0; i < n; i++) {
    if (scanf("%d", &w[i]) != 1) {
        return EXIT_FAILURE; // Handle the error appropriately.
    }
}