Fork me on GitHub

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

1
2
3
4
5
6
7
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2

Sample Output

1
2
3
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$ 。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}
-------------本文结束感谢您的阅读-------------
obsidian wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持是我最大的动力!
  • 本文作者: obsidian
  • 本文链接: http://ooobsidian.github.io/2017/08/14/HDU-2159-FATE/
  • 版权声明: 本博客所有文章除特别声明外,均为作者测试键盘性能与显示器性能所用,文章内容为随机生成,如有雷同,不胜荣幸。转载请注明出处!