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大值之和（代码可能还有问题，需要判重）
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std ; 6 7 const int N = 210, M = 5010 ; 8 9 int f[N][M],w[N],v[N] ; 10 int n, m , k ; 11 12 13 14 int main(){ 15 cin >> n >> m >> k ; 16 17 for(int i=1;i<=n;i++){ 18 cin >> v[i] >> w[i] ; 19 } 20 21 int ans = 0 ; 22 for(int h=1;h<=m;h++){ 23 memset(f,-0x3f,sizeof f) ; 24 f[h-1][0] = 0 ; 25 for(int i=h;i<=n;i++){ 26 for(int j=0;j<=k;j++){ 27 if(j>=v[i]){ 28 f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]) ; 29 }else{ 30 f[i][j] = f[i-1][j] ; 31 } 32 } 33 } 34 ans += f[n][k] ; 35 } 36 cout << ans << endl ; 37 38 return 0 ; 39 }