hdu 2159 Fate 二维费用的背包问题

缘起

开始研究二维费用背包问题. hdu 2159 Fate

分析

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
最近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

本题如果使用背包建模的话, 必须首先明确价值和费用. 每个物品就是一个游戏中的怪物.

  1. 价值是经验值
  2. 费用是消耗的忍耐度、和1条怪物的命(因为 xhd最多杀死s个怪)

所以本题的费用是二维的. 故叫做二维费用背包问题. 来一段官方的解释.

1
2
3
4
5
6
7
8
9
10
11
12
13
所谓二维费用背包问题是指:对于每件物品,具有两种不同的空间耗费,选择这件物品必须付出这两种代价,
对于每种代价都有一个背包容量,然后问背包最大价值.
动态规划模型是设W[i],U[i]是每件物品的二维费用,P[i]是价值,u,v是二维费用容量
01二维费用背包的动态规划模型是

dp[i][u][v]=max{dp[i-1][u-W[i]][v-U[i]]+P[i],dp[i-1][u][v]},

其中dp[i][u][v]是指考虑
前i件物品的取舍的时候,第一维的费用的背包容量是u,第二维的费用的背包容量是v的时候,背包的最大价值
当然上面是01二维费用背包模型,完全可以类似写出完全背包的二维费用的模型,
以及多重二维费用背包的动态归化模型.

本题显然属于二维费用完全背包

将上面的dp方程滚动数组优化一下空间复杂度得到, 这里 W[i] 是第i种怪物的忍耐度耗费, U[i]是第i种怪物的只数耗费（按本题题意，U[i]恒为1）

dp[u][v]=max{dp[u-W[i]][v-U[i]]+P[i],dp[u][v]}

初始值显然是0件物品的时候, 那么都是0.

但是本题不是标准的二维费用完全背包, 因为不是求经验值最大, 而是获取一定经验值（n）能保留的最大忍耐度. 即消耗的最小忍耐度. 也就是是求最小 而不是求最大. 所以不能直接套上面的算法模板, 而要汲取二维费用完全背包的思想. 

1
2
3
4
5
6
7
8
9
令 dp[i][u][v] 是前i个物品, 获取经验>=u, 杀死怪物只数<=v 的最小耗费忍耐度. 则
dp[i][u][v] = min{dp[i-1][u][v], dp[i-1][max(u-P[i],0)][v-U[i]]+W[i]}
其中 U[i]恒为1
即上述DP遵从的思想依旧是杀与不杀第i只怪物. 滚动数组优化一下空间复杂度
dp[u][v] = min{dp[u][v], dp[max(u-P[i],0)][v-U[i]]+W[i]}
但是我们需要重新思考初始值, 即0件物品的时候, 消耗的最少忍耐度是多少, 显然对于u>0, 都是不可能的
即初始值为inf. 即dp[u][v] = inf(1<=u<=n,0<=v<=s), dp[0][v] = 0(0<=v<=s)（杀死怪物数量为<=v, 获取经验>=0 最小消耗忍耐度显然是0）
则最后 dp[n][v]就是最少消耗的忍耐度. m-dp[n][s]就是最大剩下的忍耐度, 如果<0, 则表明不可能完成
任务

于是不难写下如下代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int read(int &x)
{
	x = 0;
	int f = 1;
	char c = getchar();
	if (!~c)
	{
		return -1;
	}
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
	x*=f;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(48+x%10);
}
const int maxn =  105, inf = 0x3f3f3f3f;
int n,m,k,s, dp[maxn][maxn], a[maxn], b[maxn];

void cp(int x, int y) // 此怪物获取经验值x, 消耗忍耐度y
{
	for (int i = 0; i<=n; i++) // 注意, i要从0开始, 而不是x, 因为dp[i][j]的含义是经验>=i,而如果当前怪物能赚取的经验x>=i的话,当然是可以的
	{
		for (int j = 1; j<= s; j++)
		{
			dp[i][j] = min(dp[i][j], dp[max(i-x, 0)][j-1]+y); // 依旧是杀与不杀
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~read(n))
	{
		read(m), read(k), read(s);
		for (int i = 1;i<=k; i++)
		{
			read(a[i]), read(b[i]);
		}
		for (int i = 1;i<=n; i++)
		{
			for (int j =0;j<=s;j++)
			{
				dp[i][j] = inf;
			}
		}
		for (int i = 0;i<=s;i++)
		{
			dp[0][i] = 0;
		} // dp初始化
		for (int i = 1;i<=k;i++)
		{
			cp(a[i], b[i]);
		}
		printf("%d\n", m-dp[n][s]<0?-1:m-dp[n][s]);
	}
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 1776kB
Length 1309
Lang C++
Submitted 2019-10-25 12:02:48
Shared
RemoteRunId 31088852