poj 2184 Cow Exhibition（01背包经典变种负数处理两种写法）

92 阅读 0 评论 61 点赞

我是靠谱客的博主害羞日记本，最近开发中收集的这篇文章主要介绍poj 2184 Cow Exhibition（01背包经典变种负数处理两种写法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

题意：

有很多牛，每只牛有一个情商和智商，要选出一些牛，智商加情商总和最大，其中智商总和和幽默度总和都不能是负数。

思路：

经典的 01背包模型，只不过需要对负数进行处理。

定义 dp[i][j] 表示的集合为：在前 i 头牛中选，且选出来的牛智商之和为 j 的所有选法。

集合的属性为：情商和的最大值。

虽然我们 dp 的是幽默值的最大值，题意要求的是智商和情商总和的最大值，没关系，在整个 dp 过程结束之后，将每个 dp[n][j] 和 i 相加看谁最大即可（始终牢记 i 表示的是智商之和）

dp 的过程中为了节省空间我们采用滚动数组优化的方式进行书写。

时间复杂度：

$O (n m)$

代码：

写法一：

由于有负数，所以可以每个体积 +1000，然后开一个 cnt 数组记录用该体积得到最大值时用了多少个 1000。

//@file	  : VS2022CodingII
//@author : Morgannr
//@date   : 2022/11/17 21:29:35

#include <iostream>
#include <vector>

using namespace std;
//#define int long long
//#define map unordered_map

//int128 ORZ

/*
__int128 read() {
	__int128 x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

void print(__int128 x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
*/
const int N = 2e5 + 10;
int n;
int dp[N], v[110], w[110];

inline void solve()
{
	while (~scanf("%d", &n))
	{
		memset(dp, 0xcf, sizeof dp);
		int sum = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d%d", v + i, w + i);
			if (v[i] <= 0 && w[i] <= 0)
			{
				--i, --n;
				continue;
			}
			v[i] += 1000;
			sum += v[i];
		}
		vector<int> cnt(sum + 5);
		dp[0] = 0;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = sum; j >= v[i]; --j)
			{
				int from = dp[j - v[i]] - (cnt[j - v[i]] + 1) * 1000 + w[i];
				int to = dp[j] - cnt[j] * 1000;
				if (to < from)//from 和 to 中每项对应
				{
					dp[j] = dp[j - v[i]] + w[i];
					cnt[j] = cnt[j - v[i]] + 1;
				}
			}
		}
		int ans = -1;
		for (int i = 0; i <= sum; ++i)
		{
			if (dp[i] >= 0 && i - cnt[i] * 1000 >= 0) {
				ans = max(ans, dp[i] + i - cnt[i] * 1000);
			}
		}
		printf("%dn", ans);
	}
}

signed main()
{
	//	ios::sync_with_stdio(false);
	//	cin.tie(nullptr), cout.tie(nullptr);

	int _ = 1; //cin >> _;

	while (_--)
	{
		solve();
	}

	return 0;
}

写法二：

//@file	  : VS2022CodingII
//@author : Morgannr
//@date   : 2022/11/17 20:49:33

#include <iostream>

using namespace std;
//#define int long long
//#define map unordered_map

//int128 ORZ

/*
__int128 read() {
	__int128 x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

void print(__int128 x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
*/
const int N = 110, M = 3e5 + 10;
int n;
int dp[M], iq[N], eq[N];

inline void solve()
{
	while (cin >> n)
	{
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d%d", &iq[i], &eq[i]);
		}
		memset(dp, 0xcf, sizeof dp);
		dp[100000] = 0;
		for (int i = 1; i <= n; ++i)
		{
			if (iq[i] >= 0)
			{
				for (int j = 200000; j >= iq[i]; --j) {
					dp[j] = max(dp[j], dp[j - iq[i]] + eq[i]);
				}
			}
			else
			{
				for (int j = max(iq[i], 0); j <= 200000; ++j) {
					dp[j] = max(dp[j], dp[j - iq[i]] + eq[i]);
				}
			}
		}

		int ans = 0;
		for (int i = 100000; i <= 200000; ++i) {
			if (dp[i] >= 0) ans = max(ans, dp[i] + i - 100000);
		}
		cout << ans << 'n';
	}
}

signed main()
{
	int _ = 1; //cin >> _;

	while (_--)
	{
		solve();
	}

	return 0;
}