完全背包
完全背包
有 n 件物品和一个最多能背重量为 w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品能重复使用，求解将哪些物品装入背包里物品价值总和最大
模板
•
组合数：外层for循环遍历物品，内层for遍历背包
•
排列数：外层for遍历背包，内层for循环遍历物品
代码块
private static void testCompletePack(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){ // 遍历物品
for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
private static void testCompletePackAnotherWay(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i <= bagWeight; i++){ // 遍历背包容量
for (int j = 0; j < weight.length; j++){ // 遍历物品
if (i - weight[j] >= 0){
dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
}
}
}
零钱兑换Ⅱ
附件不支持打印
加载失败，