【蓝桥杯2022省赛】备赛蓝桥杯经典动态规划。背包问题、背包与魔法、李白打酒加强版
一、背包问题
今天就来说一下背包问题吧,就讨论最常说的 0-1 背包问题。描述:
给你一个可装载重量为 W
的背包和 N
个物品,每个物品有重量和价值两个属性。其中第 i
个物品的重量为 w[i]
,价值为 v[i]
,现在让你用这个背包装物品,最多能装的价值是多少?
举个简单的例子,输入如下:
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 导致数组索引越界的问题
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 。
输出格式
一个整数代表答案。
样例输入">鲜梨输入
3 10 3
5 10
4 9
3 8
样例输出
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]的最大值了。
解题代码??
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 的结果.
样例输入
5 10
样例输出
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]; 至此题目完成。
解题代码??
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();
}
}
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的