【算法】完全背包

有n种物品和一个容量为m的背包，每种物品都有无限件可用。

 

第i种物品的体积是weight，价值是value。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

 

//"n" is the number of kinds.
//"m" is the capacity of the bag.
//w[]:weight , v[]:value .

for(int i=1 ; i <= n ; i++) {
    for(int val=0 ; val<=m ; val++) {
        if( val >= w[i] ) dp[val] = max( dp[val] , dp[ val-w[i] ]+v[i] );
    } 
}