HDU 2159 二维费用背包问题

一个关于打怪升级的算法问题。。

题意：一个人在玩游戏老是要打怪升级，他愤怒了，现在，还差n经验升级，还有m的耐心度(为零就删游戏不玩了。。),有m种怪，有一个最大的杀怪数s(杀超过m只也会删游戏的。。)，还给出每种怪对应的经验和消耗的耐心度。问如果能升级最多还有多少耐心度？

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2159

#include<iostream>

using namespace std;

#define N 110

#define MAX(a, b) (a > b ? a : b)

int dp[N][N];

int cost[N];//忍耐度

int value[N];//经验

int main()

{

	int n, m, k, s;//n经验,m耐心度,s最多杀怪数

	while (cin>>n>>m>>k>>s)

	{

		for (int i = 0; i<k; i++)

			cin>>value[i]>>cost[i];

		memset(dp, 0, sizeof(dp));

		int ans = 0;

		for (i = 0; i<k; i++)

		{

			for (int j = cost[i]; j<=m; j++)

			{

				for (int k = 1; k<=s; k++)

				{

					dp[j][k] = MAX(dp[j][k], dp[j - cost[i]][k - 1] + value[i]);

						if (dp[j][k] >= n && (m - j) > ans) ans = m - j;//记录最大的耐心度

				}

			}

		}

		if (dp[m][s] < n) cout<<-1<<endl;

		else cout<<ans<<endl;

	}

	return 0;

}

第一次做二维费用背包，虽然是水题，但是又感觉到算法的牛叉，除了输入输出，核心代码只有一行。

如果对背包都没什么概念的朋友，想要看懂，需要回去理解下背包，不然就。。。

巴特西

HDU 2159 二维费用背包问题

最新文章

热门文章