佩奇采药

【问题描述】

佩奇是只天资聪颖的小猪，她的梦想是成为世界上最伟大的医师。为此，她去找她的奶奶—猪小妹大陆上最有威望的医师。猪奶奶为了判断佩奇的资质，给她出了一个难题。猪奶奶把她带到一个到处都是草药的山洞里对她说：“佩奇，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一只聪明的小猪，你应该可以让采到的草药的总价值最大。”
佩奇当然能够出色地解决这个问题。如果你是佩奇，你能完成这个任务吗？

【输入文件】
输入文件medic.in 的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M<= 100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的M 行每行包括两个在1 到100 之间（包括1 和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

【输出文件】
输出文件medic.out 包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。

【胡乱分析】

这到题是一道经典的动归01背包问题。每种物品只有一件，可以考虑放或者是不放

这里用f[i][j]来表示前i个物品（不一定是所有前i个物品）恰放入一个容量为j的背包中所获得的最大价值。假设第i个物品已经放入背包了，那么此时留给背包中i-1个物品的放置空间就为背包中总容量减去第i个物品占的空间；假设第i个物品没有放入背包，那么i-1个物品还有全部的空间可以用来放置。

代码如下

f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+c[i]);

对于这道题来说，原理也是相同的，对于一种草药，只有采与不采两种选择，要是采了这颗草药，时间就得用总时间减去采这颗草药用的时间；要是没采这颗草药，采剩下的草药限制的时间仍旧等于总时间，每次操作均要求出最大价值。
代码如下

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 struct node
 8 {
 9     int shijian,jiazhi;
10 }caoyao[105];
11 int main()
12 {
13     int t,m,f[105][105];
14     memset(f,0,sizeof(f));
15     scanf("%d%d",&t,&m);
16     for(int i = 1;i <= m;i++)
17     {
18         scanf("%d%d",&caoyao[i].shijian,&caoyao[i].jiazhi);
19     }
20     for(int i = 1;i <= m;i++)
21     {
22         for(int j = t;j>0;j--)
23         {
24             if(caoyao[i].shijian <= j) 
25                 f[i][j] = max(f[i - 1][j],f[i - 1][j - caoyao[i].shijian] + caoyao[i].jiazhi);
26             else 
27                 f[i][j] = f[i - 1][j];
28         }
29     }
30     printf("%d",f[m][t]);
31     return 0;
32 }

对于以上的代码，还可以将二维数组优化成一维

f[j]=max(f[j],f[j - w[i]]+c[i]);

代码如下

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 struct node
 8 {
 9     int shijian,jiazhi;
10 }caoyao[105];
11 int main()
12 {
13     int t,m,f[105];
14     memset(f,0,sizeof(f));
15     scanf("%d%d",&m,&t);
16     for(int i = 1;i <= m;i++)
17     {
18         scanf("%d%d",&caoyao[i].shijian,&caoyao[i].jiazhi);
19     }
20     for(int i = 1;i <= m;i++)
21        for(int j = t;j >= caoyao[i].shijian;j--)
22            f[j] = max(f[j],f[j - caoyao[i].shijian] + caoyao[i].jiazhi);
23     printf("%d",f[t]);
24     return 0; 
25 }