NOIP2005-普及组复赛-第三题-采药

时间:2022-09-25 21:54:42
题目描述 Description
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗?

 输入输出格式 Input/output
输入格式:
输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式:
输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
 输入输出样例 Sample input/output
样例测试点#1
输入样例:

70 3
71 100
69 1
1 2

输出样例:

3

说明 description
对于30%的数据,M <= 10;
对于全部的数据,M <= 100。
NOIP2005普及组第三题

思路:这题要用到贪心算法(动态规划),在最少的药内求得最大的价值(和01背包问题一样),可以把总共采药时间看作是体积,每一个药是物品。

既然说到了著名的背包问题,那么就来详解一下这题吧!

初步分析

对于这个问题,一开始确实有点不太好入手。一堆的物品,每一个都有一定的质量和价值,我们能够装入的总重量有限制,该怎么来装使得价值最大呢?对于这n个物品,每个物品我们可能会选,也可能不选,那么我们总共就可能有2^n种组合选择方式。如果我们采用这种办法来硬算的话,则整体的时间复杂度就达到指数级别的,肯定不可行。

现在我们换一种思路。既然每一种物品都有价格和重量,我们优先挑选那些单位价格最高的是否可行呢?比如在下图中,我们有3种物品,他们的重量和价格分别是10, 20, 30 kg和60, 100, 120。

NOIP2005-普及组复赛-第三题-采药

那么按照单位价格来算的话,我们最先应该挑选的是价格为60的元素,选择它之后,背包还剩下50 - 10 = 40kg。再继续前面的选择,我们应该挑选价格为100的元素,这样背包里的总价值为60 + 100 = 160。所占用的重量为30, 剩下20kg。因为后面需要挑选的物品为30kg已经超出背包的容量了。我们按照这种思路能选择到的最多就是前面两个物品。如下图:

NOIP2005-普及组复赛-第三题-采药

按照我们前面的期望,这样选择得到的价值应该是最大的。可是由于有一个背包重量的限制,这里只用了30kg,还有剩下20kg浪费了。这会是最优的选择吗?我们看看所有的选择情况:

NOIP2005-普及组复赛-第三题-采药

很遗憾,在这几种选择情况中,我们前面的选择反而是带来价值最低的。而选择重量分别为20kg和30kg的物品带来了最大的价值。看来,我们刚才这种选择最佳单位价格的方式也行不通。

动态规划

既然前面两种办法都不可行,我们再来看看有没有别的方法。我们再来看这个问题。我们需要选择n个元素中的若干个来形成最优解,假定为k个。那么对于这k个元素a1, a2, ...ak来说,它们组成的物品组合必然满足总重量<=背包重量限制,而且它们的价值必然是最大的。因为它们是我们假定的最优选择嘛,肯定价值应该是最大的。假定ak是我们按照前面顺序放入的最后一个物品。它的重量为wk,它的价值为vk。既然我们前面选择的这k个元素构成了最优选择,如果我们把这个ak物品拿走,对应于k-1个物品来说,它们所涵盖的重量范围为0-(W-wk)。假定W为背包允许承重的量。假定最终的价值是V,剩下的物品所构成的价值为V-vk。这剩下的k-1个元素是不是构成了一个这种W-wk的最优解呢?

我们可以用反证法来推导。假定拿走ak这个物品后,剩下的这些物品没有构成W-wk重量范围的最佳价值选择。那么我们肯定有另外k-1个元素,他们在W-wk重量范围内构成的价值更大。如果这样的话,我们用这k-1个物品再加上第k个,他们构成的最终W重量范围内的价值就是最优的。这岂不是和我们前面假设的k个元素构成最佳矛盾了吗?所以我们可以肯定,在这k个元素里拿掉最后那个元素,前面剩下的元素依然构成一个最佳解。

现在我们经过前面的推理已经得到了一个基本的递推关系,就是一个最优解的子解集也是最优的。可是,我们该怎么来求得这个最优解呢?我们这样来看。假定我们定义一个函数c[i, w]表示到第i个元素为止,在限制总重量为w的情况下我们所能选择到的最优解。那么这个最优解要么包含有i这个物品,要么不包含,肯定是这两种情况中的一种。如果我们选择了第i个物品,那么实际上这个最优解是c[i - 1, w-wi] + vi。而如果我们没有选择第i个物品,这个最优解是c[i-1, w]。这样,实际上对于到底要不要取第i个物品,我们只要比较这两种情况,哪个的结果值更大不就是最优的么?

在前面讨论的关系里,还有一个情况我们需要考虑的就是,我们这个最优解是基于选择物品i时总重量还是在w范围内的,如果超出了呢?我们肯定不能选择它,这就和c[i-1, w]一样。

另外,对于初始的情况呢?很明显c[0, w]里不管w是多少,肯定为0。因为它表示我们一个物品都不选择的情况。c[i, 0]也一样,当我们总重量限制为0时,肯定价值为0。

这样,基于我们前面讨论的这3个部分,我们可以得到一个如下的递推公式:

NOIP2005-普及组复赛-第三题-采药

有了这个关系,我们可以更进一步的来考虑代码实现了。我们有这么一个递归的关系,其中,后面的函数结果其实是依赖于前面的结果的。我们只要按照前面求出来最基础的最优条件,然后往后面一步步递推,就可以找到结果了。

我们再来考虑一下具体实现的细节。这一组物品分别有价值和重量,我们可以定义两个数组int[] v, int[] w。v[i]表示第i个物品的价值,w[i]表示第i个物品的重量。为了表示c[i, w],我们可以使用一个int[i][w]的矩阵。其中i的最大值为物品的数量,而w表示最大的重量限制。按照前面的递推关系,c[i][0]和c[0][w]都是0。而我们所要求的最终结果是c[n][w]。所以我们实际中创建的矩阵是(n + 1) x (w + 1)的规格。

部分背包问题

和前面使用动态规划方法解决问题不一样。因为这里是部分背包问题,我们可以采用前面讨论过的一个思路。就是每次选择最优单位价格的物品,直到达到背包重量限制要求。

以前面的示例来看,我们按照这种方式选择的物品结果应该如下图:

NOIP2005-普及组复赛-第三题-采药

现在,我们从实现的角度再来考虑一下。我们这里的最优解是每次挑选性价比最高的物品。对于这一组物品来说,我们需要将他们按照性价比从最高到最低的顺序来取。我们可能需要将他们进行排序。然后再依次取出来放入背包中。假定我们已经有数组v,w,他们已经按照性价比排好序了。

一点改进:

在前面我们挑选按照性价比排好序的物品时,排序消耗了主要的时间。在这里,我们是否真的需要去把这些物品排序呢?在某些情况下,我们只要选择一堆物品,保证他们物品重量在指定范围内。如果我们一次挑出来一批这样的物品,而且他们满足这样的条件是不是更好呢?这一种思路是借鉴快速排序里对元素进行划分的思路。主要过程如下:

1. 求每个元素的单位价值,pi = vi /wi。然后数组按照pi进行划分,这样会被分成3个部分,L, M, N。其中L < M < N。这里L表示单位价值小于某个指定值的集合,M是等于这个值的集合,而N是大于这个值的集合。

2. 我们可以首先看N的集合,因为这里都是单位价值高的集合。我们将他们的重量累加,如果WN的重量等于我们期望的值W,则N中间的结果就是我们找到的结果。

3. 如果WN的重量大于W,我们需要在N集合里做进一步划分。

4. 如果WN的重量小于W,我们需要在N的基础上再去L的集合里划分,找里面大的一部分。

这样重复步骤1到4.

这里和快速排序的思路基本上差不多,只是需要将一个分割的集合给记录下来。其时间复杂度也更好一点,为O(N)。这里就简单的描述下思路,等后续再将具体的实现代码给补上。

总结

我们这里讨论的两种背包问题因为问题的不同其本质解决方法也不同。对于0-1背包来说,他们构成了一个最优解问题的基础。我们可以通过从最小的结果集递推出最终最优结果。他们之间构成了一个递归的关系。而对于部分背包问题来说,我们可以考虑用贪婪算法,每次选择当前看来最优的结果。最终也构成了一个最优的结果。一个小小的前提变化,问题解决的思路却大不同。里面的思想值得反复体会。

代码如下:

#include <stdio.h>
#include <string.h>
int f[],w[],v[];
int max(int x,int y)
{
if(x>y) return x;
else return y;
}
int main()
{
int t,m,i,j;
memset(f,,sizeof(f));
scanf("%d %d",&t,&m);
for(i=;i<=m;i++)
{
scanf("%d %d",&w[i],&v[i]);
}
for(i=;i<=m;i++)
{
for(j=t;j>=w[i];j--)
{
if(w[i]<=t)
f[j]=max(f[j-w[i]]+v[i],f[j]);
}
}
printf("%d\n",f[t]);
return ;
}

NOIP2005-普及组复赛-第三题-采药的更多相关文章

  1. NOIP2014-普及组复赛-第三题-螺旋矩阵

    题目描述 Description 一个n行n列的螺旋矩阵可由如下方法生成: 从矩阵的左上角(第1行第1列)出发,初始时向右移动:如果前方是未曾经过的格子,则继续前进,否则右转:重复上述操作直至经过矩阵 ...

  2. NOIP2002-普及组复赛-第三题-选数

    题目描述 Description 已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n).从 n 个整数中任选 k 个整数相加,可分别得到一系列的和.例如当 n=4,k=3,4 个整 ...

  3. NOIP2005普及组第3题 采药 (背包问题)

    NOIP2005普及组第3题 采药 时间限制: 1 Sec  内存限制: 128 MB提交: 50  解决: 23[提交][状态][讨论版][命题人:外部导入] 题目描述 辰辰是个天资聪颖的孩子,他的 ...

  4. NOIP2005普及组第4题 循环

    NOIP2005普及组第4题 循环 时间限制: 1 Sec  内存限制: 128 MB提交: 27  解决: 6[提交][状态][讨论版][命题人:外部导入] 题目描述 乐乐是一个聪明而又勤奋好学的孩 ...

  5. &lbrack;NOIP2005&rsqb; 普及组 循环

    陶陶摘苹果 校门外的树 采药 以上三道都不是重点 循环 题目描述 乐乐是一个聪明而又勤奋好学的孩子.他总喜欢探求事物的规律.一天,他突然对数的正整数次幂产生了兴趣. 众所周知,2的正整数次幂最后一位数 ...

  6. NOIP2018普及组复赛游记

    2018年11月10日,NOIP2018普及组复赛. 这是我初中阶段最后一次复赛了. 和往常一样,我们在预定的早上7点,没有出发. 10分钟之后,人终于到齐了,于是出发了,一路无话. 到了南航,合照三 ...

  7. NOIP2016普及组复赛解题报告

    提高组萌新,DAY1DAY2加起来骗分不到300,写写普及组的题目聊以自慰. (附:洛谷题目链接 T1:https://www.luogu.org/problem/show?pid=1909 T2:h ...

  8. noip普及组考纲&plus;样题合集——初级篇(OIer必看)

    很明显我是想发提高组合集的.普及组考纲……用发么. 当然如果你想看的话也可以,就一点点: 递归.排序…… 很明显上面那都不是重点.普及组只要掌握搜索.二分.单调队列.数学.随机化等等,一等奖没问题的, ...

  9. 【动态规划】Vijos P1104 采药(NOIP2005普及组第三题)

    题目链接: https://vijos.org/p/1104 题目大意: T时间,n个物品,每个耗时ti,可获得收益ci,求最大收益. 题目思路: [动态规划] 01背包裸题.一维二维都过了,放个一维 ...

随机推荐

  1. GET和POST可传递的值到底有多大?

    前日,看到这个问题了. 没有深入了解.我的常识里面get最大传递的值为256b,post 是2M.这是很久以前不知在哪看到的.于是又百度一下.看到两篇文章装过来看看: 浅谈 HTTP中Get与Post ...

  2. 第1组UI组件:布局管理器

    1 布局管理的来源 为了让UI在不同的手机屏幕上都能运行良好----不同手机屏幕的分辨率/尺寸并不完全相同,如果让程序手动控制每个组件的大小.位置,会给编程带来巨大的麻烦.为了解决这个问题.andro ...

  3. 码云分布式之 Brzo 服务器

    摘要: 码云是国内最大的代码托管平台,为了支持更大的用户规模,开发团队也在对一些组件进行大规模的重构. 前言 码云是国内最大的代码托管平台.码云基于 Gitlab 5.5 开发,经过几年的开发已经和官 ...

  4. 【转】Android 混淆代码总结

    http://blog.csdn.net/lovexjyong/article/details/24652085 为了防止自己的劳动成果被别人窃取,混淆代码能有效防止被反编译,下面来总结以下混淆代码的 ...

  5. &lbrack;置顶&rsqb; Objective-C &comma;ios&comma;iphone开发基础&colon;UIAlertView使用详解

    UIAlertView使用详解 Ios中为我们提供了一个用来弹出提示框的类 UIAlertView,他类似于javascript中的alert 和c#中的MessageBox(); UIAlertVi ...

  6. swiper display&colon;none 后 在显示 滑动问题

    一般这种问题  必须在本身元素  或者父元素  显示出来  然后调用swiper实例 或者只需加两行 observer:true, // 修改swiper自己或子元素时,自动初始化swiper obs ...

  7. 微信小程序之滑动日历展示

    滑动日历效果 效果预览 实现要求:顶部固定悬浮的是获取未来一周的日期,分为上下两部分,上面部分显示星期,下面则显示具体日期.今天则显示今天,可点击头部具体日期,可向左向右滑动. 实现代码 顶部日历 页 ...

  8. Windows 环境下进行的jenkins持续集成

    一台服务器作为代码仓库,一条服务器做持续集成代码仓库目前常见的github.gitlab.gitee持续集成常用Jenkins 服务器的配置这边都以Windows为例进行介绍 1. 安装Jenkins ...

  9. 分布式架构的基石&period;简单的 RPC 框架实现&lpar;JAVA&rpar;

    前言 RPC 的全称是 Remote Procedure Call,它是一种进程间通信方式.允许像调用本地服务一样调用远程服务. 学习来源:<分布式系统架构:原理与实践> - 李林锋 1. ...

  10. Typescript 基础知识

    Typescript 就是 Javascript 的超集,所以首先你要知道 Javascript 基础知识 类型注解 类型注解在TypeScript中是记录函数或变量约束的简便方法. // 布尔值 l ...