前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >常用算法思想之动态规划的多条件记忆思路

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

作者头像
爬蜥
发布2019-07-09 14:39:26
5150
发布2019-07-09 14:39:26
举报
文章被收录于专栏:爬蜥的学习之旅

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

背包问题

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

DP(i,X)=max(DP(i-1,X),DP(i-1,X-S_i)+V_i \space if\space S_i\leq S)
DP(i,X)=max(DP(i-1,X),DP(i-1,X-S_i)+V_i \space if\space S_i\leq S)

假设有如下示例:

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月05日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 背包问题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档