加载中…POJ PKU 2184 背包
(2011-07-10 16:22:50)
标签：
pojpku2184背包it |
分类： 动态规划 |
题目描述：
n组数字，每组2个数字a，b，可正可负，让你从n组选出一个子集，让这个子集的所有ab之和最大，同时a的和，b的和都不能为负。
结题报告：
不能为负是最后检测的时候才用到，还是01背包，方法：
dp[i][j]表示到第i组的时候，a数字的和为j时的最大的b值
dp[i][j] = max(dp[i - 1][j - a] + b, dp[i - a][j])
可以用滚动的一维数组即可，注意a为负数时从小到大扫描。
代码如下：
while(scanf("%d", &n) !=
EOF)
{
for(int i = 0; i
< 200001; i++) dp[i] = inf;
dp[100000] = 0;
for(int i = 0; i
< n; i++)
{
int a, b;scanf("%d%d", &a,
&b);
if (a >= 0)
{
for(int j =
200000; j >= a; j--)
if (dp[j - a] != inf) dp[j] =
max(dp[j - a] + b, dp[j]);
}
else
{
for(int j =
0; j <= 200000 + a; j++)
if (dp[j - a] != inf) dp[j] =
max(dp[j - a] + b, dp[j]);
}
}
int jeo = 0;
for(int i = 100000; i
<= 200000; i++)
if (dp[i] != inf
&& dp[i] >= 0) jeo =
max(jeo, dp[i] + i - 100000);
printf("%d\n", jeo);
}
return
0;
n组数字，每组2个数字a，b，可正可负，让你从n组选出一个子集，让这个子集的所有ab之和最大，同时a的和，b的和都不能为负。
结题报告：
不能为负是最后检测的时候才用到，还是01背包，方法：
dp[i][j]表示到第i组的时候，a数字的和为j时的最大的b值
dp[i][j] = max(dp[i - 1][j - a] + b, dp[i - a][j])
可以用滚动的一维数组即可，注意a为负数时从小到大扫描。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf -0x7fffffff
int dp[200001], n;
int main()
{
}
喜欢
0
赠金笔
前一篇：一个错误。。。
后一篇：POJ PKU 2157 广搜