锐客网

  1. 首页 > it技术 > >

noip2005|noip2005 二维采药---恰 （01背包）

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

如果你是辰辰，你能完成这个任务吗？
输入 输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。 输出 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 样例输入

70 3 71 100 69 1 1 2

样例输出
3


讲解：这是一道01背包的经典入门题（背包的经典资料当属《背包九讲》），那么先让我们来整理一下思路，把问题变得更加简单。 对于动态规划，我曾经的竞赛教练说过：“动规就是枚举，枚举最后一步”，按我的理解，也即是列举所有策略，枚举策略。在这道题中，对于物品i来讲，就只有两种策略：要、不要。如果要，那么就要消耗时间v[i]，获得价值w[i]。 对于这道题，显然我们要求出在拥有m个物品，时间为t的情况下所能得到的最大价值。这要如何去求解呢？根据上面所讲，每一件物品就只有两种策略，显然我们可按照次序枚举物品。初始时有效时间为0，代表任何物品都没有装入背包，我们把这看做第0层。枚举到第一个物品，这是第一层，显然第一层会有两种情况，第一种时间为0，价值为0，这是未选物品1，上一层的有效时间0，价值0的状态延续到这一层；第二种，时间为0+v[i]，价值为0+w[i]，这是要选择物品1放入背包，并由上一层的时间0，价值0的状态衍生而来。然后以此类推，最终到第m个物品时，我们就可得到，用m个物品可以组合成的各有效时间，以及其对应的价值，而答案就在这之中。 到这里，对这道题的思路就很明晰了，首先，我们需要一个物品一个物品的进行枚举，自然也就有了先后顺序，这就是dp中阶段的先后；其次，对于每个物品，只有两种选择方案，有限的选择方案构成策略；之后，我们可用f[i][j]记录各个状态，表示在只拥有前i个物品，时间恰为j的情况下，所能得到的最大价值，状态可定义。由此，我们可以得到结论：这道题可用dp解决。 状态转移方程：f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i]}，前一个代表不选择物品i，时间恰为j，后一个代表选择了物品i，时间恰为j。
#include #include #define maxn1 (100+10) #define maxn2 (1000+10) using namespace std; int t,m,v[maxn1],w[maxn1],f[maxn1][maxn2]; void work() { int i,j,ans; scanf("%d%d",&t,&m); for(i=1; i<=m; i++)scanf("%d%d",&v[i],&w[i]); f[0][0]=1; for(i=1; i<=m; i++) for(j=0; j<=t; j++) if(j>=v[i] && f[i-1][j-v[i]]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); else f[i][j]=f[i-1][j]; for(ans=0,j=0; j<=t; j++)ans=max(ans,f[m][j]); printf("%d\n",ans); }int main() { work(); return 0; }


代码解析： 1.如何判断f[i][j]是否有效，即判断前i个物品，是否能组合出体积恰为j的情况。对于这个，我投了点懒，因为根据我的实践，在win7、linux的系统中，数组变量的初始值是默认为0的，而非数组则好像是随机的。c++是非常灵活的，它可以把int类型的数据当作bool类型来用，int型数据值为0，那它的bool也为0，即false，否则为1，即true。 int i=2113131; if(i)printf("%d\n",1); 这段程序会输出结果1。 现在，问题就变简单了，如果f[i][j]有效，那它的值肯定大于0，所以：
if(j>=v[i] && f[i-1][j-v[i]]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); else f[i][j]=f[i-1][j];


这里要注意一点，为了程序容错性更好，j>=v[i]要写在前面，避免出现下标越界的情况（虽然c++中下标越界并不会报错，并且有些时候也并不影响程序的正确性，但我认为一个程序员应当养成严谨的做题习惯，才能避免以后出现更多其他问题）。 因为f[0][0]也是有效的，但f[0][0]的初始值为0，所以可以先把f[0][0]赋值为1，最后的答案减1输出即可。 2.j的枚举必须从0到t，因为有些没有用到的f[i-1][j]的数据也需要搬到第i层，不然就会出现断层，导致程序出错。
最后在输出答案时，j的枚举必须从0开始，因为有可能存在背包里一个物品也没装的情况。 3.是标准输入输出（scanf、printf）的头文件，头文件里面包含了函数max。 我个人是不赞成有些教练让学生死背头文件，然后每次写程序就先写一堆的头文件这种大撒网式的做法。我提倡的用到那些函数，就写那些头文件，知其然也知其所以然，这样才是对个人能力的提高。 （有问题的欢迎在下方留言，关于背包问题的都行，并不一定是关于这道题或者01背包）







    推荐阅读


    上一篇：noip2005|noip2005 一维采药---非恰 （01背包）

    下一篇：关于自动化测试的思考-起源于百人计划分享