完全背包
k 个怪物， 每打一个怪物有经验， 消耗忍耐度。 可以把 经验看做是 价值 w[i], 忍耐度看做是体积 v[i].
题目转化为， 用一个体积为 m 的背包，装一些物品（每一个物品可以装无限次）， 取得的最大价值。
裸的完全背包题目。
本题要点：
1、n <= 100, 可开二维数组。 但是，这里有个限制，取的物品总数不能超过 s 个。所用，需要一个数组 mp[MaxN][MaxN]
来计数， 以保证取物品，不超过 s 个。
2、f[i][j] 表示 从前i个物品中，选出总体积是j的物品，最大价值
mp[i][j] 表示计算 f[i][j] 时候，一共选择了多少物品
3、 最后要求输出的是，在消耗最少的体积的情况下，能够获得 n 的价值。 答案就是，算出来的每一个 f[i][j],
找出一个 f[i][j] >= n 时候， m - j 的最大值（剩余体积，就是剩余忍耐度）
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 110, INF = 0xcfcfcfcf;
int n, m, k, s;
int w[MaxN], v[MaxN]; // 价值，体积
int f[MaxN][MaxN]; // f[i][j] 表示 从前i个物品中，选出总体积是j的物品，最大价值
int mp[MaxN][MaxN]; // mp[i][j] 表示计算 f[i][j] 时候，一共选择了多少物品void solve()
{
int ans = -1;for(int i = 1; i <= k; ++i){
for(int j = 0; j <= m; ++j){
f[i][j] = INF;mp[i][j] = 0;}}f[0][0] = 0;for(int i = 1; i <= k; ++i){
for(int j = 0; j <= m; ++j){
f[i][j] = f[i - 1][j];mp[i][j] = mp[i - 1][j];}for(int j = v[i]; j <= m; ++j){
if(mp[i][j - v[i]] < s) // 还能加一个{
if(f[i][j] < f[i][j - v[i]] + w[i]){
f[i][j] = f[i][j - v[i]] + w[i];mp[i][j] = mp[i][j - v[i]] + 1;}}}for(int j = 0; j <= m; ++j){
if(f[i][j] >= n){
ans = max(ans, m - j); }}}printf("%d\n", ans);
}int main()
{
while(scanf("%d%d%d%d", &n, &m, &k, &s) != EOF){
for(int i = 1; i <= k; ++i){
scanf("%d%d", &w[i], &v[i]);}solve();}return 0;
}/* 10 10 1 10 1 1 10 10 1 9 1 1 9 10 2 10 1 1 2 2 *//* 0 -1 1 */