ранец код - не работает в некоторых случаях

Question

Мой код выглядит следующим образом:

#include<stdio.h> 
    int max(int a,int b) 
{ 
     return a>b?a:b; 
} 
int Knapsack(int items,int weight[],int value[],int maxWeight) 
{ 
     int dp[items+1][maxWeight+1]; 
     /* dp[i][w] represents maximum value that can be attained if the maximum weight is w and 
      items are chosen from 1...i */ 
     /* dp[0][w] = 0 for all w because we have chosen 0 items */ 
     int iter,w; 
     for(iter=0;iter<=maxWeight;iter++) 
     { 
       dp[0][iter]=0; 
     } 
     /* dp[i][0] = 0 for all w because maximum weight we can take is 0 */ 
     for(iter=0;iter<=items;iter++) 
     { 
       dp[iter][0]=0; 
     } 
     for(iter=1;iter<=items;iter++) 
     { 
       for(w=0;w<=maxWeight;w=w+1) 
       { 
         dp[iter][w] = dp[iter-1][w]; /* If I do not take this item */ 
         if(w-weight[iter] >=0) 
         { 
           /* suppose if I take this item */ 
           dp[iter][w] = max((dp[iter][w]) , (dp[iter-1][w-weight[iter]])+value[iter]); 
         } 
       } 

     } 
     return dp[items][maxWeight]; 
} 
int main() 
{ 
     int items=9; 
     int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10}; 
     int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87}; 
     int iter; 
     int i; 

     int maxWeight=180; 

     for (i=0;i<10;i++){ 
      value[i] = value[i]*weight[i]; 
     } 

     printf("Max value attained can be %d\n",Knapsack(items,weight,value,maxWeight)); 
} 

Мой ранец код работает, когда

items=12; 
int weight[/*items+1*/13]={60, 20, 20, 20, 10, 20, 10, 10, 10, 20, 20, 10}; 
int value[/*items+1*/13]={48, 77, 46, 82, 85, 43, 49, 73, 65, 48, 47, 51}; 

где он возвратил правильный вывод .

Но он не вернулся правильный выход, когда

items=9; 
int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10}; 
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87}; 

, где он вернулся выход , правильный вывод должен быть . Из наблюдения программа как-то пропустила первое значение (вес = 60, значение = 73). Я проверил код несколько раз, но я просто не могу найти, что случилось. Может кто-нибудь объяснить мне, почему? Спасибо!

Answer 1

В вашем коде вы пытаетесь получить доступ за пределами индекса для weight и value массива. Когда iter достигает значения 9, weight[iter] и value[iter] выходит за пределы индекса. Я думаю, что в C вы просто получаете некоторое количество мусора из-за доступа к индексу, но в Java, которое выдает исключение. Изменение кода в вашей внутренней for петли для:

dp[iter][w] = dp[iter-1][w]; /* If I do not take this item */ 
if(w-weight[iter - 1] >=0) 
{ 
    /* suppose if I take this item */ 
    dp[iter][w] = maximum((dp[iter][w]) , (dp[iter-1][w-weight[iter - 1]])+value[iter - 1]); 
} 

, и он будет работать нормально.

Answer 2

int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10}; 
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87}; 

Ваши массивы имеют длину 10, но вы заполняете всего 9 записей. Поэтому последняя запись заполняется 0. How to initialize all members of an array to the same value?

int weight[/*items+1*/10]={60, 10, 20, 20, 20, 20, 10, 10, 10, 0}; 
int value[/*items+1*/10]={73, 81, 86, 72, 90, 77, 85, 70, 87, 0}; 

Но вы пытаетесь получить доступ к индексам (от 1 до 9) в вашем алгоритме.

Вместо этого попробуйте заполнять все записи:

int weight[/*items+1*/10]={0, 60, 10, 20, 20, 20, 20, 10, 10, 10}; 
int value[/*items+1*/10]={0, 73, 81, 86, 72, 90, 77, 85, 70, 87}; 

EDIT:
Первый случай дает правильный выход, так как в этом случае первая запись не входит в оптимальное решение.