思路:要解决的子问题不仅仅是数量的变化,判断的条件也会变化,选择同时记住子问题和变化的条件,存下所有变化条件下子问题的最优结果,作为父问题的解答
选择的方案总共有两种,那种方式使得价值最大就选择对应的装的方式
假设有如下示例:
总共有3个物件,背包限量为5kg。物件分别为
A价值10元,4kg
B价值4元,2kg
C价值7元,3kg
复制代码
背包里头刚开始什么都没有,也就是刚开始的时候什么都不拿,背包中的价值都是0。
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | ||||||
B | ||||||
C |
横轴表示背包能装的重量,纵轴表示物件,每个单元格表示对应重量中背包能装的最大价值
假设这个时候只有一个物件A,它的重量是4kg,根据背包能装的条件必须是背包的容量至少是4kg,否则无论价值是多少,容量不够肯定不能装
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | ||
B | ||||||
C |
列为0表示容量为0
此时容量已经到达4了,有两个选择
可以看到装A带来的价值更大
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | |
B | ||||||
C |
当容量到达5时,和4做一样的考虑,有DP(0,1)+10=0+10>DP(0,5)=0,因而继续选择装A价值更大
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | ||||||
C |
物件A的选择已经穷尽,此时可以看做'A已经装在背包了'。考虑物件B,它的重量为2kg
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | 0 | 0 | 4 | 4 | ||
C |
当容量为4的时候情况出现了一点变化
可以看到A,B两者在容量为4时,选择只装A是更优的选择,同样的情况适用于容量5
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | 0 | 0 | 4 | 4 | 10 | 10 |
C |
然后考虑C,此时背包已经考虑过装A,B的情况
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | 0 | 0 | 4 | 4 | 10 | 10 |
C | 0 | 0 | 4 |
当容量为3时
DP(2,0)表示在容量为0的情况下,A+B都考虑是否装的最优价值
得出只装C更好
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | 0 | 0 | 4 | 4 | 10 | 10 |
C | 0 | 0 | 4 | 7 |
当容量为4时
不装C更好
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | 0 | 0 | 4 | 4 | 10 | 10 |
C | 0 | 0 | 4 | 7 | 10 |
当容量为5时
装C更好
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
A | 0 | 0 | 0 | 0 | 10 | 10 |
B | 0 | 0 | 4 | 4 | 10 | 10 |
C | 0 | 0 | 4 | 7 | 10 | 11 |
由此可以得到结论,容量为5,当前条件下最优的价值是11。 代码如下
public static void main (String[] args) throws Exception{
//code
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int round=Integer.parseInt(br.readLine());
for(int r=1;r<=round;r++){
//物件的个数
int N=Integer.parseInt(br.readLine());
//背包的容量
int W=Integer.parseInt(br.readLine());
String[] vStrs=br.readLine().split(" ");
String[] wtStrs=br.readLine().split(" ");
int[] v=new int[N+1];
int[] wt=new int[N+1];
for(int i=0;i<N;i++){
//物件的价值
v[i]=Integer.parseInt(vStrs[i]);
//物件的重量
wt[i]=Integer.parseInt(wtStrs[i]);
}
int[][] dpV=new int[N+1][W+1];
for(int i=1;i<=N;i++){
for(int j=1;j<=W;j++){
int result=dpV[i-1][j];
if(wt[i-1]<=j){
result=Math.max(v[i-1]+dpV[i-1][j-wt[i-1]],dpV[i-1][j]);
}
dpV[i][j]=result;
}
}
System.out.println(dpV[N][W]);
}
}
复制代码
总共的耗时时间为O(NW),与背包的容量和物件的个数都有关。