1. 编程圈首页
  2. 文库
  3. 后端开发

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

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

背包问题

总共n个物件,每个物件的重量S_i,是个Integer,每个物件价值V_i,背包能装下的重量为S,求每次获取最大价值的装法。
分析如下:背包能装下的重量是有限的,如果物件本身的重量是大于背包的能装范围,价值再大也不能装,对于剩余重量小于背包能装范围:

  • 假设选择装物件A,此时获取价值为V_a,剩余能装重量 $S-S_a
  • 假设选择不装物件A,此时可以在剩余的物件里面选择一个能装的

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

DP(i,X)=max(DP(i-1,X),DP(i-1,X-S_i)+V_i space ifspace S_ileq S)
  • X表示当前背包能装的量
  • i-1表示背包当前已经装的物件
  • S_i表示当前的物件重量
  • DP(i-1,X)表示不装物件
  • DP(i-1,X-S_i)+V_i则表示当前选择装能带来的价值
  • DP(i-1,X-S_i)则表示在剩余重量下的最大能装的价值

假设有如下示例:

总共有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。
代码如下

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

伪多项式运行时间

从上面看到背包问题需要的时间为O(ns),其中s表示背包的最大容量,一个物件的最大允许放的大小就是S,存放在电脑上起码需要 logS 的空间。而总共的个数有 n 个需要处理,所以花销的空间大小为 O(nlogS),假设logS=b,即输入大小为 O(nb),那么运行时间为O(n.2^b),也就是随着输入的变大,运行时间会变成指数增长,但是如果b很小,就是多项式运行时间,这种称为伪多项式运行时间。

发布者:编程圈,转转请注明出处:https://www.bianchengquan.com/article/66283.html

发表评论

登录后才能评论