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
#include <iostream>
#include <algorithm>
#include <cstring> using namespace std ; const int N = , M = , C = ; int f[N][M],v[C],w[C] ;
int n,m,V ; int main(){
cin >> n >> m >> V ; memset(f,,sizeof f) ;
f[][] = ;//f[j][k],表示体积恰好为j时的第k大值
for(int i=;i<=n;i++){
cin >> v[i] >> w[i] ;
} for(int i=;i<=n;i++){
for(int j=V;j>=v[i];j--){
int now[],c1=,c2=,idx= ;//now缓存合并最大k值的结果，避免计算的时候出现串扰
while(c1+c2<=m+){
if(f[j][c1]>f[j-v[i]][c2] + w[i]){
now[++idx] = f[j][c1++] ;
}else{
now[++idx] = f[j-v[i]][c2++] + w[i] ;
}
}
for(int h=;h<=m;h++){
f[j][h] = now[h] ;
}
}
}
int ans = ;
for(int i=;i<=m;i++){
ans += f[V][i] ;
} cout << ans << endl ; return ;
}