POJ 2184 DP

题目链接:http://poj.org/problem?id=2184

有 $n$ 头牛,每头牛都有智商($S_i$)和情商($F_i$)两种属性。有的牛的智商或者情商可能为负。现在要从这些牛中挑选一些出来,令他们的智商之和为 $TS$,情商之和为 $TF$,求 $TS + TF$ 的最大值,同时要求 $TS \geq 0$ 且 $TF \geq 0$。

思路

变种的背包问题,令 $dp[i][j]$ 为前 $i$ 头牛,智商之和($TS$)等于 $j$ 时,情商之和($TF$)的最大值。

$$
dp[i][j] = max(dp[i-1][j], dp[i-1][j-S_i] + F_i)
$$

传统的背包问题定义 $dp[i][j]$ 为从前 $i$ 个物品中选取重量不超过 $j$ 时的最大价值,而本题的 $dp[i][j]$ 为前 $i$ 头牛,智商之和等于$j$ 时,情商之和的最大值。

最后只要选出 $max(dp[n][j] + j)$ 即可 $(j\geq0 \& dp[n][j]\geq0)$。

具体实现时注意两点:

  1. 由于 $j$ 可能为负,因此需要给整体加上偏移 Offset
  2. 初始化时,$dp$ 数组应该置为无穷小
  3. 使用滚动数组来优化空间
2184.cppview raw
#include <iostream>
#include <stdio.h>
#include <cstring>
#define maxn 105
#define maxs 1050
#define offset maxn * maxs
using namespace std;

int s[maxn], f[maxn], dp[2][maxn * maxs * 2];

int main() {
int n; cin >> n;
for (int i = 0; i < n; i++)
scanf("%d %d", &s[i], &f[i]);

memset(dp, -0x3f, sizeof dp);
dp[0][offset] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < maxn * maxs * 2; j++)
if (j - s[i] >= 0 && j - s[i] < maxn * maxs * 2)
dp[(i + 1) % 2][j] = max(dp[i % 2][j], dp[i % 2][j - s[i]] + f[i]);
else
dp[(i + 1) % 2][j] = dp[i % 2][j];

int ans = 0;
for (int j = 0; j < maxn * maxs; j++)
if (dp[n % 2][j + offset] >= 0)
ans = max(ans, j + dp[n % 2][j + offset]);
cout << ans << endl;
return 0;
}