完全背包问题
完全背包问题和01背包的区别就在于每一个物品可取的次数,01背包每个物品只能取一次,完全背包每个物品能取无数次。
而01背包为了保证每个物品只取一次,在遍历背包的时候需要倒序遍历,这样才能保证之前的状态都是初始状态,没有添加过物品,利用之前的状态时就不会将同一个物品进行重复添加。
在完全背包中,就需要每个物品能取多次,于是解除遍历背包时的倒序限制就行。
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int M=sc.nextInt();
int N=sc.nextInt();
int[] weight=new int[M];
int[] value=new int[M];
int bagsize=N;
for(int i=0;i<M;i++){
weight[i]=sc.nextInt();
value[i]=sc.nextInt();
}
maxValue(weight,value,bagsize);
}
public static void maxValue(int[] weight,int[] value,int bagsize){
int[] dp=new int[bagsize+1];
for(int i=0;i<weight.length;i++){
for(int j=weight[i];j<bagsize+1;j++){
dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
}
}
System.out.println(dp[bagsize]);
}
}
在完全背包中,在求装满指定容量背包的组合总数的时候,遍历顺序非常重要,只求组合总数的话,先遍历物品,后遍历背包,因为先遍历物品的话,每次都会将前一个物品先添加进去,只会出现{1,2}这样的组合,不会出现{2,1}的组合。因为当前物品层依赖上一个物品层传递下来的状态,上一个物品层,就只会又上一个物品层和其之前的物品层的组合。不会有之后物品层的值放入组合中。
而将遍历顺序颠倒,先遍历背包,后遍历物品,以物品{1,2,3}为例,装满容量为4的背包,y轴为物品,x轴为背包。
0 | 1 | 2 | 3 | 4 | |
0 | 1 | 1 | 1 | 2 | 4 |
1 | 1 | 1 | 2 | 3 | 6 |
2 | 1 | 1 | 2 | 4 | 7 |
当背包容量为3,假如已取物品1,也就是先放入重量为2的物品,剩余只能取重量为1的组合了,就出现了{2,1},而假如已取的是物品0,也就是先放入重量为1的物品,剩余只能取重量为2的组合,因为在上一个状态遍历了物品1,已经有了重量2的组合,就出现了{1,2}和{1,1,1}的组合了。
零钱兑换 II
题中只要求求组合总数,不讲究顺序。
动规五部曲,改变下遍历顺序
class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
dp[0]=1;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<amount+1;j++){
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
}
组合总和 Ⅳ
讲究顺序
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp=new int[target+1];
dp[0]=1;
for(int j=1;j<target+1;j++){
for(int i=0;i<nums.length;i++){
if(j>=nums[i]){
dp[j]+=dp[j-nums[i]];
}
}
}
return dp[target];
}
}