HDU 2159 FATE(完全背包)

题目

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

分析

这道题是完全背包问题,完全背包就是在 $N$ 种物品中选取若干件(同一种物品可多次选取)放在空间为 $V$ 的背包里,每种物品的体积为 $C_1 ,C_2 ,… ,C_n$ ,与之相对应的价值为 $W_1,W_2,…,W_n$ .求解怎么装物品可使背包里物品总价值最大。

子问题定义:$F[i][j]$ 表示前 $i$ 种物品中选取若干件物品放入剩余空间为 $j$ 的背包中所能得到的最大价值。

根据第 $i$ 种物品放多少件进行决策,其状态转移方程为:
$$F[i][j]=max(F[i-1][j-k \times C[i]]+k \times W[i])$$

对于这道题,我们设 $F[i][j]$ 为杀第 $j$ 只怪时耐久度为 $i$ 的最大经验值,完全背包类型:有 $N$ 种物品和一个容量为 $V$ 的背包,每种物品都有无限件可用。放入第 $i$ 种物品的耗费的空间是 $C_i$ ,得到的价值是 $W_i$ 。


代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
int n,m,k,s,dp[105],cnt[105];
struct node
{
    int a,b;
}mo[110];
bool cmp(node c,node d)
{
    return c.a>d.a;
}
int main()
{
    while(cin>>n>>m>>k>>s)
    {
        int ans=-1;
        for(int i=0;i<k;i++)
            cin>>mo[i].a>>mo[i].b;
        sort(mo,mo+k,cmp);     //对经验值进行排序
        clr(dp,0);
        clr(cnt,0);
        for(int i=0;i<k;i++)  //从第1个怪到第k个怪
        {
            for(int j=mo[i].b;j<=m;j++)   //耐久度从1到m,耐久度为0时经验必为0
            {
                if(cnt[j-mo[i].b]>=s)
                    continue;
                if(dp[j-mo[i].b]+mo[i].a>dp[j])
                {
            
                    dp[j]=dp[j-mo[i].b]+mo[i].a;
                    if(dp[j]>=n&&(m-j)>ans)
                        ans=m-j;
                    cnt[j]=cnt[j-mo[i].b]+1;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
本文作者:Author:     文章标题:HDU 2159 FATE(完全背包)
本文地址:https://alphalrx.cn/index.php/archives/54/     
版权说明:若无注明,本文皆为“LRX's Blog”原创,转载请保留文章出处。
Last modification:November 2nd, 2019 at 02:43 pm
给作者赏一杯奶茶吧!

Leave a Comment