HDU - 2159 - FATE(完全背包）

FATE

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16395 Accepted Submission(s): 7698

Problem Description
最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

Input
输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

Output
输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。

Sample Input
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2

Sample Output
0
-1
1

Author
Xhd

Source
2008信息工程学院集训队——选拔赛

Recommend
linle | We have carefully selected several similar problems for you: 1203 1171 2191 1114 2571


题意：

• 多组数据。每组数据先输入 n，m，k，s。
• n : 升级所需要的经验。
• m : 所拥有的耐力。
• k : 怪的种类。
• s : 最多能杀的怪的数量。
• 接下来有 k 行，每行输入 a , b。
• a : 杀死第 i 个怪所能获得的经验。
• b : 杀死第 i 个怪所要消耗的耐力。
  
  问：在满足所杀的怪的数量不超过 s , 所消耗的耐力不超过 m 时，最多剩下多少耐力？
  
  

解题思路：

• 这道题可以转化为完全背包来做。m 等价于背包的容量。a 等价于物品的价值。b 等价于物品的体积。但是这道题有一点要注意的地方，就是题目要求所杀的怪的数量不能超过 s。
• 所以需要增加一个 cnt[j]。cnt[j] : 前 i 种怪中，花费耐力不超过 j ，并且在获得最多经验时，最少杀的怪的数量。其他就直接按完全背包来做。
• dp[j] : 前 i 种怪中，花费耐力不超过 j 时，最多能获得的经验。
• 转移方程看代码。
• 最后的答案就是在满足条件下，选一个剩下最多的经验。
  
  优先级：所获经验 > 杀怪数量
  
  

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

int dp[105];// dp[j] : 前 i 种怪中，花费耐力不超过 j 时，最多能获得的经验。
int cnt[105];// cnt[j] : 前 i 种怪中，花费耐力不超过 j ，并且在获得最多经验时，最少杀的怪的数量。
int a[105],b[105];

int main(){
    int n,m,k,s;
    while(cin >> n >> m >> k >> s){
        for(int i = 1;i <= k;i++){
            cin >> a[i] >> b[i];
        }
        memset(dp,0,sizeof(dp));
        memset(cnt,0,sizeof(cnt));
        for(int i = 1;i <= k;i++){
            for(int j = b[i];j <= m;j++){
                if(dp[j] < dp[j - b[i]] + a[i]){//转移方程(优先经验)
                    dp[j] = dp[j - b[i]] + a[i];
                    cnt[j] = cnt[j - b[i]] + 1;
                }
                else if(dp[j] == dp[j - b[i]] + a[i]){//转移方程
                    cnt[j] = min(cnt[j],cnt[j - b[i]] + 1);
                }
            }
        }
        int ans = -1;
        for(int i = 0;i <= m;i++){
            if(dp[i] >= n && cnt[i] <= s) ans = max(m - i,ans);
        }
        cout << ans << endl;
    }
}