一、背包问题

二、背包与魔法

         问题描述

解题思路

解题代码

三、李白打酒加强版数

         问题描述

解题步骤

解题代码

一、背包问题

今天就来说一下背包问题吧，就讨论最常说的 0-1 背包问题。描述：

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 w[i]，价值为 v[i]，现在让你用这个背包装物品，最多能装的价值是多少？

举个简单的例子，输入如下：

1
2
3
4
N = 4, W = 5
wt = [2, 2, 4,2]
val = [4, 1, 3,2]

算法返回 6，选择前两件物品装进背包，总重量 4小于 W，可以获得最大价值 6。

题目就是这么简单，一个典型的动态规划问题。这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。这就是 0-1 背包这个名词的来历。

第一步要明确两点，「状态」和「选择」。

        先说状态，只要给几个物品和一个背包的容量限制，就形成了一个背包问题呀。所以状态有两个，就是「背包的容量」和「可选择的物品」。再说选择，对于每件物品，选择就是「装进背包」或者「不装进背包」。

第二步要明确 dp 数组的定义。

首先看看刚才找到[状态]和[选择]，有两个，也就是说我们需要一个二维 dp 数组。

dp[i][w] 的定义如下：对于前 i 个物品，背包的容量为 w情况下可以装的最大价值是 dp[i][w].

第三步，根据「选择」，思考状态转移的逻辑。

简单说就是「把物品 i 装进背包」和「不把物品 i 装进背包」用代码体现出来呢？

这就要结合对 dp 数组的定义，看看这两种选择会对状态产生什么影响：

先重申一下刚才我们的 dp 数组的定义：

dp[i][w] 表示：对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]。

如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。

如果你把这第 i 个物品装入了背包，那么 dp[i][w] 应该等于 v[i-1] + dp[i-1][w - w[i-1]]。

综上就是两种选择，我们都已经分析完毕，也就是写出来了状态转移方程

 我用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了 w - w[i-1] 可能小于 0 导致数组索引越界的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int bag(int W, int N, int[] wt, int[] v) {
    assert N == wt.length;
    // 定义dp二维数组
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 这种情况下只能选择不装入背包   角标越界问题
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + v[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }
    
    return dp[N][W];
}

至此，背包问题就解决了，相比而言，我觉得这是比较简单的动态规划问题，因为状态转移的推导比较自然，基本上你明确了  dp 数组的定义，就可以理所当然地确定状态转移了。

二、背包与魔法

问题描述

小蓝面前有 N 件物品, 其中第 i 件重量是 Wi​, 价值是 Vi​ 。她还有一个背包, 最大承重是 M 。

小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?

特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 K, 同时价值秝倍。(当然小蓝也可以不使用魔法)

输入格式

第一行包含 3 个整数 N、M 和 K 。

以下 N 行, 每行两个整数 Wi​ 和 Vi​ 。

输出格式

一个整数代表答案。

样例输入">鲜梨输入

1
2
3
4
5
3 10 3
5 10
4 9
3 8

样例输出

1
2
26

样例说明

选择第二件和第三件物品, 同时对第二件物品使用魔法。

评测用例规模与约定

对于 30% 的数据, 1≤N,M,K≤100.

对于 100% 的数据, 1≤N≤2000,1≤M,K≤10000,0≤Wi​,Vi​≤10000.

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

解题思路????????

问题描述????

小蓝面前有 N 件物品, 其中第 i 件重量是 Wi​, 价值是 Vi​ 。她还有一个背包, 最大承重是 M 。

小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?

特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 K, 同时价值秝倍。(当然小蓝也可以不使用魔法)

思路解析????

其实这道题就是经典的背包问题，只是在背包问题的基础上增加了使用魔法k

首先明确选择和状态。选择就是[装进背包]和[不装进背包],状态就是使用魔法和不使用魔法

第二就是明确dp数组的定义。

dp[w][0]就是背包在容量为w的情况下不使用魔法的价值；dp[w][1]就是背包容量在w的情况下使用魔法的价值;

第三就是写出状态转移方程

首先没有使用魔法的情况下：

        如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[w][0] 应该等于 dp[w][0]，继承之前的结果。

        如果你把这第 i 个物品装入了背包，那么 dp[w][0] 应该等于 v[i-1] + dp[w - wi[i-1]][0]。

第二如果使用了魔法的情况下：

         如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[w][1] 应该等于 dp[w][1]，继承之前的结果。

        如果你把这第 i 个物品装入了背包，那么 dp[w][1] 应该等于 v[i-1] + dp[w - wi[i-1]][1]。

最大价值就是dp[w][0]和dp[w][1]的最大值了。

解题代码????????

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt(),m=scan.nextInt(),k=scan.nextInt();
        int[] w=new int[n+1],v=new int[n+1];
        for(int i=1;i<=n;i++){
          w[i]=scan.nextInt();
          v[i]=scan.nextInt();
        }
        int[][] dp=new int[m+1][2];//在背包剩余多少质量下有没有使用魔法价值
        for(int i=1;i<=n;i++){
          for(int j=m;j>=w[i];j--){
            dp[j][0]=Math.max(dp[j][0],dp[j-w[i]][0]+v[i]);
            if(j>=w[i]+k){//防止角标越界
dp[j][1]=Math.max(Math.max(dp[j][1],dp[j-w[i]][1]+v[i]),dp[j-w[i]-k][0]+2*v[i]);
            }
          }
        }
        System.out.println(Math.max(dp[m][0],dp[m][1]));
        scan.close();
    }
}

三、李白打酒加强版数

问题描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:

无事街上走，提显去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

输入格式

第一行包含两个整数 N 和 M.

输出格式

输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果.

样例输入

1
2
5 10

样例输出

1
2
14

样例说明

如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

评测用例规模与约定

对于 40%40% 的评测用例: 1≤N,M≤10 。

对于 100%100% 的评测用例:1≤N,M≤100 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题步骤????????

问题描述????

一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:无事街上走，提显去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

思路解析????

首先是明确状态和选择。此处就是遇到花和遇到店，状态是剩余酒的多少.

第二是定义dp数组。dp[n][m][[k]表示的是遇到了n家店，m次花，剩余的酒为k斗,dp数组的值就是k斗酒的顺序次数。

第三是描述状态转移方程

首先我们明确最后酒是喝完了，那么最后一次的话酒是1斗，遇到花。

base case

dp[0][1][1]=1

dp[0][2][0]=1

dp[0][0][2]=1

其次我们可以从酒量入手

如果酒量k是奇数的话。那么上次是遇到了花 。dp[i][j][k]+=dp[i][j-1][k+1];  dp[i][j][k]+=dp[i-1][j][k/2];

如果酒量k是偶数的话。那么上次是遇到了花或者店  dp[i][j][k]+=dp[i][j-1][k+1];

至此题目完成。

解题代码????????

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static final int mod=(int)1e9+7;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        /*
        首先这是上次蓝桥杯困到我的题目。
        dp[n][m][k] 表示n店m花剩k酒。
        这里的状态有店、花、酒
        题目要求最后一次必须是花（喝完酒），因此倒数第二次肯定是1.因此答案是dp[n][m-1][1];
        状态方程：当酒为奇数斗时，你s上次一定是遇到店。（原因是需要保证酒最后被喝完）
        当酒是偶数斗时，你上次可能遇到店或者花
        */
        int n=scan.nextInt();
        int m=scan.nextInt();
        int[][][] dp=new int[n+1][m+1][m+2];
        dp[0][0][2]=1;
        dp[0][1][1]=1;
        dp[0][2][0]=1;
        for(int i=1;i<=n;i++){
          for(int j=0;j<=m;j++){
            for(int k=0;k<=m;k++){
              if(k%2==0){//店或者花
                if(j>0)dp[i][j][k]+=dp[i][j-1][k+1];
                if(i>0)dp[i][j][k]+=dp[i-1][j][k/2];
              }else{//店
                if(j>0)dp[i][j][k]+=dp[i][j-1][k+1];
              }
              dp[i][j][k]%=mod;
            }
          }
        }
        System.out.println(dp[n][m-1][1]%mod);
        scan.close();
    }
}

最后

以上就是英俊裙子最近收集整理的关于【蓝桥杯2022省赛】备赛蓝桥杯经典动态规划。背包问题、背包与魔法、李白打酒加强版一、背包问题二、背包与魔法三、李白打酒加强版数的全部内容，更多相关【蓝桥杯2022省赛】备赛蓝桥杯经典动态规划内容请搜索靠谱客的其他文章。