dz网站自己做的模板放在哪里,2345网址导航安装,wordpress文章详情展示不了,中国十大私企蓝桥杯备赛 | 洛谷做题打卡day26 文章目录 蓝桥杯备赛 | 洛谷做题打卡day26题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路 题解代码我的一些话 [NOIP2001 普及组] 装箱问题 题目描述 有一个箱子容量为 V V V#xff0c;同时有 n n n 个物品#xff0c;每… 蓝桥杯备赛 | 洛谷做题打卡day26 文章目录 蓝桥杯备赛 | 洛谷做题打卡day26题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路 题解代码我的一些话 [NOIP2001 普及组] 装箱问题 题目描述 有一个箱子容量为 V V V同时有 n n n 个物品每个物品有一个体积。 现在从 n n n 个物品中任取若干个装入箱内也可以不取使箱子的剩余空间最小。输出这个最小值。 输入格式 第一行共一个整数 V V V表示箱子容量。 第二行共一个整数 n n n表示物品总数。 接下来 n n n 行每行有一个正整数表示第 i i i 个物品的体积。 输出格式 共一行一个整数表示箱子最小剩余空间。 样例 #1 样例输入 #1 24
6
8
3
12
7
9
7样例输出 #1 0提示 对于 100 % 100\% 100% 数据满足 0 n ≤ 30 0n \le 30 0n≤30 1 ≤ V ≤ 20000 1 \le V \le 20000 1≤V≤20000。 【题目来源】 NOIP 2001 普及组第四题 思路
这道题看似是搜索但是可以用背包做。
题目要求求出最小的剩余空间也就是要求出最大的可装重量
这样我们可以将一个物体的重量当作它的价值进而将题目转变为一个基本的01背包问题
有一个箱子容量为V正整数0V20000同时有n个物品0n30每个物品有一个体积正整数和一个价值等于体积。
要求n个物品中任取若干个装入箱内使总价值最大。
对于每一个物体都有两种状态装 与不装
那么对于任意重量m的最大价值 f (m) max ( f ( m - w[i] ) w[i], f (m) )w为重量即价值
其中f ( m - w[i] ) 指在装了物品i后箱子的剩余容量能装的最大重量
f ( m - w[i] ) w[i] 指在在装了物品i后箱子能装的最大重量
题解代码 学会利用新知自己多试试并尝试积攒一些固定解答方案debug以下是题解代码 ~ #includecstdio
using namespace std;
int m,n; m即箱子容量V
int f[20010];
int w[40];
int main(){int i,j;scanf(%d%d,m,n);for(i1;in;i){scanf(%d,w[i]);}for(i1;in;i){for(jm;jw[i];j--){ 注意这里必须是从m到w[i]否则一个物体会被多次装入箱子见例1if(f[j]f[j-w[i]]w[i]){f[j]f[j-w[i]]w[i];}}}printf(%d\n,m-f[m]);
}我的一些话 今天学习动态规划dp属于比较难的部分需要多动脑多思考思路还是很好掌握的虽然一次性AC有一定难度需要通盘的考虑和理解以及扎实的数据结构基础才能独立写出AC代码。但无论难易大家都要持续做题保持题感喔一起坚持(o´ωo) 如果有非计算机专业的uu自学的话关于数据结构的网课推荐看b站上青岛大学王卓老师的课讲的很细致有不懂都可以私信我喔 总结来说思路很重要多想想多在草稿纸上画画用测试数据多调试debug后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎评论留言一起成长
