多重背包问题II
总体积是m，每个小物品的体积是A[i] ，每个小物品的数量是B[i]，每个小物品的价值是C[i]求能够放入背包内的最大物品能够获得的最大价值
和上一个很类似
上一题体积就是价值，这里的价值是单独定义了
状态转移方程
不放A[i]
f[i][j] =f[i-1][j]
放A[j]
可放多个设为k，
k = min(j/A[i],B[i])
f[i][j] = f[i-1][j- ki*A[i]] + ki*C[i] 0<=ki<=k 取最大值
完全背包问题时候：0<=ki*A[i]<=m
public class Solution { public int backPack(int m, int[] A,int[] B ,int[] C) { // write your code here int[] P = new int[m+1];// P[i][j] 前i个物品放在j的空间中的最大价值 for(int i = 0;i< A.length; i++){ for(int j = m;j>=1;j--){ if(j>=A[i]){ int k = j/A[i];// 该物品最大可以放k个，然而限制条件最大是B[i] k = Math.min(k,B[i]);// 取最小值 while(k>=0){ if(j>=A[i]*k){ P[j] =Math.max(P[j], P[j-k*A[i]] + k*C[i]); } k--; } } else P[j] = Math.max(P[j],P[j]); } } return P[m]; } /** * 多重背包问题 * 总体积是m，每个小物品的体积是A[i] ，每个小物品的数量是B[i] * * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] 0 开始的 A是 * @return: The maximum size */ public int backPack1(int m, int[] A,int[] B ,int[] C) { // write your code here int[][] P = new int[A.length+1][m+1];// P[i][j] 前i个物品放在j的空间中的最大价值 for(int i = 0;i< A.length; i++){ for(int j = m;j>=1;j--){ if(j>=A[i]){ int k = j/A[i];// 该物品最大可以放k个，然而限制条件最大是B[i] k = Math.min(k,B[i]);// 取最小值 while(k>=0){ if(j>=A[i]*k){ P[i+1][j] =Math.max(P[i+1][j], P[i][j-k*A[i]] + k*C[i]); } k--; } } else P[i+1][j] = Math.max(P[i][j],P[i+1][j]); } } return P[A.length][m]; } public static void main(String[] args){ int m = 10;//100;// int[] A=new int[]{1,2,3,4}; int[] B=new int[]{2,3,1,4}; int[] C=new int[]{2,13,4,2}; int sum = new Solution().backPack(m, A,B,C); System.out.println(sum); }} 10：45
100:55