Почему это решение DP для задачи о рюкзаке 0/1 не дает правильного вывода с GCC?

Question

#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" одна и та же программа создает допустимый вывод для того же ввода.

Так что это заставляет меня поверить, что я не придерживаюсь стандартов Си. Это так?

Answer 1

Когда вы инициализируете 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. Измените код для последовательного использования индексации на основе 0.

Кроме того, вы должны проверить возвращаемое значение scanf, иначе неверный ввод даст странные результаты вместо ошибки.

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

Answer 2

может быть с тем же кодом .. включая будет работать .. просто установите 0-й индексированный элемент в -infinity с помощью (имя массива) [0] = - INT_MAX.