2：完全背包

完全背包

完全背包的场景： 一个有固定体积V的背包，有一些物品，往包里装，在不超过包的体积的情况下，使得包里装的价值最大。每个物品可以重复装。 N:表示可以装进包里的东西的个数 V:表示这个背包的体积 weight[N]:表示重量的数组 value[N]:表示价值的数组 dp[V]:表示包里的总价值的数组

举例：

weight = [3, 2, 2, 8, 4, 2, 2, 7] value = [3, 4, 2, 7, 5, 3, 1, 6] V = 12, N = 8; 那么这个表格为：

i \ j12345678910111210033366699912200333666999123023456789101112402345688101112135023456881011121360234568810111213724681012141618202224824681012141618202224

行代表包剩余的体积为j，列代表物品的id 所以最大的价值为24，即全部取7号物品 代码实现为：

class Bag_All{ public static void main(String[] args) { int []value = {0, 3, 2, 2, 8, 4, 2, 2, 7}; int []weight = {0, 3, 4, 2, 7, 5, 3, 1, 6}; int a = bagall(8, 12, value, weight); System.out.println(a); } public static int bagall(int N, int V, int []value, int []weight){ int []dp = new int[64]; for(int i = 1; i <= N; i++){ for(int j = weight[i]; j <= V; j++){ dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } return dp[V]; } public static int max(int a, int b){ if(a > b) return a; else return b; } }