Problem H. Wiki with Herbal Medicine
Input file: standard input Time limit: 1 second
Output file: standard output Memory limit: 256 megabytes
题目描述
前方高能，又见采草药！
Wiki是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为
师。
Wiki觉得上一次拜访的医师有点水，为此，他经过多方打探，终于找到了一个口碑与医术极佳的医师拜
师学艺。当然，医师为了判断他的资质，同样也给他出了一道难题。
医师把他带到一个到处都是草药的山洞里对他说： "孩子，这个山洞里有n种不同的草药，每一株草药都
有一定的体积，每一株也有它自身的价值。我会给你m个体积都为v的背篓，你可以采到一些草药。如果
你是一个聪明的孩子，请满足以下几个要求：
(1)必须正好把这m个背篓放满药材(每个背篓里面的药材体积之和恰好等于v)；
(2)每种草药有无限株，每种药材最多只能放一个在每个背篓里，每种药材可以放在多个背篓里面（当
然，草药是不能切分的），每个背篓里面可以放多种药材， 但是任意两个背篓里面的药材种类不能完全相
同；
(3)在满足上述条件的前提下，请计算出能采到的药材价值之和(药材价值之和等于m个背篓里面的药材
价值加起来的总和)。
如果你是Wiki，你能完成这个任务吗？
Input
第 一 行 三 个 正 整 数n; m; v， 分 别 表 示 山 洞 里 面 药 材 的 种 类， 背 篓 的 个 数 以 及 每 个 背 篓 的 体
积(1 <= n <= 200; 1 <= m <= 50; 1 <= v <= 5000)
接下来输入n行wi; ci(1 <= wi <= 5000; 1 <= ci <= 10000),表示每种药材的体积和其对应的价值
Output
输出1个整数，表示在满足医师规定的条件下， Wiki可以采到草药的最大总价值
Sample
| standard input | standard output |
| 5 2 10 3 12 7 20 2 4 5 6 1 1 | 57 |
思路：
01背包求前k大值之和，注意初始化，体积恰好为v
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 5 using namespace std ; 6 7 const int N = 5000, M = 60, C = 210 ; 8 9 int f[N][M],v[C],w[C] ; 10 int n,m,V ; 11 12 int main(){ 13 cin >> n >> m >> V ; 14 15 memset(f,128,sizeof f) ; 16 f[0][1] = 0 ;//f[j][k],表示体积恰好为j时的第k大值 17 for(int i=1;i<=n;i++){ 18 cin >> v[i] >> w[i] ; 19 } 20 21 for(int i=1;i<=n;i++){ 22 for(int j=V;j>=v[i];j--){ 23 int now[60],c1=1,c2=1,idx=0 ;//now缓存合并最大k值的结果，避免计算的时候出现串扰 24 while(c1+c2<=m+1){ 25 if(f[j][c1]>f[j-v[i]][c2] + w[i]){ 26 now[++idx] = f[j][c1++] ; 27 }else{ 28 now[++idx] = f[j-v[i]][c2++] + w[i] ; 29 } 30 } 31 for(int h=1;h<=m;h++){ 32 f[j][h] = now[h] ; 33 } 34 } 35 } 36 int ans = 0 ; 37 for(int i=1;i<=m;i++){ 38 ans += f[V][i] ; 39 } 40 41 cout << ans << endl ; 42 43 return 0 ; 44 }