用动态规划法求解简单的0-1背包问题 oj题目P1208 采药

news/2025/1/12 20:41:44/

题目描述

 

 算法设计与分析

这题是典型的可以用动态规划来求解的问题,假设总共有n株草药,这题就是想要让我们求\sum xi*vi,1<=i<=n,其中xi的值不是0就是1表示选择摘或者不摘第i株草药,摘第i株草药的话,xi=1,否则xi=0;而vi表示的是第i株草药的价值;那么这题就是为x1,x2.......xn,赋予一组值使得\sum xi*vi最大,暂时把为x1,x2.......xn赋予一组值得过程称作一个决策;那么构造dp数组,dp[i][j]得值表示,当剩余采摘草药得时间还有j时,已经为x1,x2......xi做了一个决策,即前i株草药已经决策好哪些采摘那些不采摘,且这个决策使得\sum xi*vi最大,那么最终dp数组中最后一个数组元素得值就是我们需要求得值

程序源代码以及运行结果截图

//采药,用动态规划的思路来解,对于每一株草药要么采摘,要么不采摘,看看采摘和不采摘哪一个的哪一个是最优的选择,构造dp数组,对于0-1背包的问题用贪心算法求解不出来#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define M 100
#define T 1000//此题用动态规划的方法来解,构造的dp数组的含义是,dp[i][j]表示当时间容量剩余j时对于前i个物品采摘决策所得到的最优的解
int max(int a, int b)
{if (a > b)return a;elsereturn b;
}
int dp[M + 2][T + 2];           //辅助数组,用于求解dp问题int vdp[M + 2][T + 2];         //用于存放背包剩余体积的数组int main()
{int t;    //表示可以进行采草药的总的时间int m;   //表示山洞里的草药的总的数目int time[M];int value[M];while (scanf("%d%d",&t,&m) != EOF){for (int i = 0; i < m; i++){scanf("%d%d", &time[i], &value[i]);}for (int i = 1; i <= m; i++){for (int j = 1; j <= t; j++){//还要记录以下放进背包的东西容量是否超了没有,你这种做法相当于假定背包容量无限if (j < time[i - 1]){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i - 1]] + value[i - 1]);      //对于一株草药选择采摘和不采摘时看哪一种价值会更大}}}printf("%d\n", dp[m][t]);}return 0;}

运行结果截图

 这题其实不是很难,会记录是因为我以前遇到过一样的题,那题我用贪心思路去解,好巧不巧的是oj上面给的测试用例刚好让我用贪心得思路得到了正确得结果,但是对于0-1背包问题用贪心思路是解不出来得,贪心思路得到的结果也不一定是最优得结果,因为贪心策略总是做出对当前来说最好的选择,也就是求每一个的局部最优解,但是这些局部最优解合起来是不是全局最优解这是不一定的,所以贪心算法需要证明其正确性,要部分背包问题才可以用贪心得策略来做,在上算法课的时候老师讲0-1背包问题的解法时也只讲了回溯法,分支界限法,以及动态规划法,但是当时做题目的时候用贪心法碰巧在某些测试用例上得出了正确结果就以为0-1背包问题可以用贪心策略来解,这算是记录一下初学算法时的一些坑吧,我觉得收获还挺大的,分享给你们,下面是我用贪心算法解0-1背包的例子http://t.csdn.cn/mYmTy,感兴趣的可以去看一下,这篇博文用错误的算法思路得到了正确的结果,像本题用我上面这篇博文的贪心思路就得不出正确结果,所谓正确的结果是指在oj上面运行通过了,但是能通过应该只是因为oj给的测试用例很凑巧让我通过了不代表我的算法思路正确,事实上我的算法思路不正确,这篇博文是对它的一个更正;

祝学习进步,生活愉快!


http://www.ppmy.cn/news/242065.html

相关文章

数据结构基础-栈

栈 概述 计算机科学中&#xff0c;stack 是一种线性的数据结构&#xff0c;只能在其一端添加数据和移除数据。习惯来说&#xff0c;这一端称之为栈顶&#xff0c;另一端不能操作数据的称之为栈底&#xff0c;就如同生活中的一摞书 先提供一个栈接口 public interface Stack…

参考网站+大神blog

​ 参考网站 视频类 音视频开发中文网&#xff1a;https://ffmpeg.0voice.com/ 语言类 C语言中文网&#xff1a;http://c.biancheng.net/ 大神BLOG 实战大神 Brendan Gregg&#xff1a;https://www.brendangregg.com/             http://dtrace.org/blogs/…

图解Redis中的9种数据结构

如图所示&#xff0c;Redis中提供了9种不同的数据操作类型&#xff0c;他们分别代表了不同的数据存储结构。 图2-17 数据类型 String类型 String类型是Redis用的较多的一个基本类型&#xff0c;也是最简单的一种类型&#xff0c;它和我们在Java中使用的字符类型什么太大区别&…

DMBOK知识梳理for CDGA/CDGP——第四章 数据架构(附常考知识点)

关 注ghz“大数据食铁兽”&#xff0c;回复“知识点”获取《DMBOK知识梳理for CDGA/CDGP》常考知识点&#xff08;第四章 数据架构&#xff09; 第四章 数据架构 第四章是CDGA|CDGP考试的重点考核章节之一&#xff0c;分值占比高&#xff0c;知识点比较密集&#xff0c;重点…

仅1cm厚!华硕发布全球最薄13.3英寸笔记本

近日&#xff0c;华硕发布了新款Zenbook S 13 OLED&#xff0c;官方称其为世界最纤薄的13.3英寸OLED笔记本电脑。 据悉&#xff0c;这款电脑的厚度仅有1cm&#xff0c;重量也仅有1kg&#xff0c;相较其他同尺寸的笔记本&#xff0c;确实更加轻薄。 材质上&#xff0c;这款笔记本…

人才是企业决胜的关键,企业进行全球布局时,如何解决人才供应问题?

在一带一路政策和双循环政策的引领下&#xff0c;企业全球化已成为大型企业发展过程中的必经之路&#xff0c;更需要优秀的全球化人才来支撑战略布局。但海外环境错综复杂&#xff0c;各地政策、员工管理又各不相同&#xff0c;直接将本部优秀人才布局海外往往会造成“水土不服…

惠普电脑适合学计算机的学生,最适合学生用的笔记本电脑是什么

最实用&#xff0c;最合适学生用的笔记本是什么呢?下面由学习啦小编给你做出详细的最适合学生用的笔记本介绍!希望对你有帮助! 学生笔记本电脑推荐一&#xff1a; 华硕S46E3217CA-SL 推荐理由&#xff1a;时尚流行的超级本&#xff0c;外观时尚超薄&#xff0c;蓄电时间长。华…

苹果发布全球最薄笔记本。

北京时间1月16号凌晨1点&#xff0c;在美国旧金山,传言中的MacBook Air正式发布,今天已经开始接受预订,售价为1799美金.这款世界上最轻薄的笔记本电脑只有 0.16-0.7 英寸,银色机身,无光驱,甚至连LAN口都没有,可以放进一个信封.多触点鼠标,13.3吋LED背光显示器,全尺寸键盘.80G标…