【アルゴリズム】完全バックパック

n種類の品物と容量mのリュックサックがあり、それぞれの品物には無限のものがあります.
 
i番目の品物の体積はweightで、価値はvalueです.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの体積の合計がリュックサックの容量を超えず、価値の合計が最大になります.
 

1 //"n" is the number of kinds.

2 //"m" is the capacity of the bag.

3 //w[]:weight , v[]:value .

4 

5 for(int i=1 ; i <= n ; i++) {

6     for(int val=0 ; val<=m ; val++) {

7         if( val >= w[i] ) dp[val] = max( dp[val] , dp[ val-w[i] ]+v[i] );

8     } 

9 }