常用算法思想之动态规划的多条件记忆思路

思路：要解决的子问题不仅仅是数量的变化，判断的条件也会变化，选择同时记住子问题和变化的条件，存下所有变化条件下子问题的最优结果，作为父问题的解答

背包问题

选择的方案总共有两种，那种方式使得价值最大就选择对应的装的方式

假设有如下示例：

代码语言：javascript复制

总共有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，剩余容量是5
• 装A，带来的价值是10，损失的容量是4，剩余容量是0，在原来容量是1且没有物件可装的情况下，DP(0,0)它的价值是0

可以看到装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

• 只有在背包有容量装时，才能带来价值
• 当容量为2时，A是装不下的，此时原始背包的价值为0，装能带来价值
• 当容量为3是，还是只能装下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
C

当容量为4的时候情况出现了一点变化

• 不装B，此时背包的已经装下了A，而且价值DP(1,4)=10
• 装B，带来的价值为4，剩余容量为3，而在容量为3时，初始的价值为DP(1,3)=0,总价值为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的时候，原始背包什么都没有装，而且容量也达不到C的重量
• 当容量为2的时候，仍然装不下C，而不装C，从A,B中的结果来看，可以得到的最佳价值为DP(2,2)=4

	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时

• 不装C，原始价值为DP(2,3)=4
• 装C，原始价值为 7 DP(2,0)=7

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，原始价值为DP(2,4)=10
• 装C，带来价值7，损失重量3，剩余1，总价值为DP(2,1) 7=7

不装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，价值为DP(2,5)=10
• 装C，带来价值7，损失重量3，剩余重量2，总价值DP(2,2) 7=4 7=11

装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。 代码如下

代码语言：javascript复制

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),与背包的容量和物件的个数都有关。

dp

0 人点赞