Cow Exhibition （0-1背包变形2）

"Fat and docile, big and dumb, they look so stupid, they aren't much
fun..."
- Cows with Guns by Dana Lyons

The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.

Input

* Line 1: A single integer N, the number of cows

* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.

Output

* Line 1: One integer: the optimal sum of TS and TF such that both TS and TF are non-negative. If no subset of the cows has non-negative TS and non- negative TF, print 0.

Sample Input

Sample Output

Hint

OUTPUT DETAILS:

Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value
of TS+TF to 10, but the new value of TF would be negative, so it is not
allowed.

题目大意：给你一组聪明smart和funny值，求怎样选择可以使得smart和funny的和最大，且smart和funny都为非负；

题目分析：这道题一开始想到用DFS来着，但想了一下发现范围太大。又考虑了动态规划，发现可以转化为0-1背包问题，但遇到了很多阻碍，一直没有写出来，看来一下别人的题解以后发现，思路虽然出来了，但是一些细节上的困难没有将明白，导致我自己想了好久。为了方便大家理解和我以后可能会回来看，我就把难点好好讲一下。把smart看成重量，funny作为价值。

1.第一个难点在于怎么处理负数的情况。题目给我们的范围是n<=100,m<=1000.所以总数和的范围就是（-100000~100000），那我们不防将这个数整体向右平移100000个单位，这样范围就变成了（0~100000~200000），以100000为界分开了。但是负数带个我们的难点还没有解决，由于存在负数，我们无法用0或-1作为dp[]的初始值，所以我们可以用负无穷，例如-9999999（正无穷可以吗？）这样的数来做初始值，但是又不能全部为负无穷。我们知道初始值是我们更新得基础，全为负无穷会导致状态转移的时候，无法进行正常的更新（即使更新也是一个很靠近负无穷的数）。所以我们必须将dp[100000]这个分界点标记为0.这样我们的初步动作就做完了。

struct  Cow
{
    int sm, fu;//牛的smart和funny
}cow[maxn];

for (int i = 1; i <= n; i++)
        scanf("%d %d", &cow[i].sm, &cow[i].fu);
    for (int i = 0; i <= maxnv * 2; i++)
        dp[i] = -9999999;
    dp[maxnv] = 0;

View Code

2.关键的地方就在这里了：还是负数导致的，hh，为什么呢？我们来看状态转移方程：dp[j] = max(dp[j], dp[j - cow[i].sm] + cow[i].fu);红色部分中，如果sm为负的话，-号就成了+号，逆序跟新，就会造成从前往后，而后面的是我们已经跟新过的，造成重复和错误跟新。所以我们要将其分开来。

for (int i = 1; i <= n; i++)
{
    if (cow[i].sm > 0)//为正逆序
    {
        for (int j = maxnv * 2; j >= cow[i].sm; j--)
            dp[j] = max(dp[j], dp[j - cow[i].sm] + cow[i].fu);
    }
    else//为负正序
    {
        for (int j = 0; j - cow[i].sm <= maxnv * 2; j++)
            dp[j] = max(dp[j], dp[j - cow[i].sm] + cow[i].fu);
    }
}

View Code

3.最后一个点在于输出，这个我困了很久，理解起来挺有难度的，不过想一下还是会明白的。之前我们以100000为中间点，并作为跟新的基础点。那很显然在这个点的右边，都是smart相加后为整数的点，那为什么呢？我们就拿-5 7 /8 -6这两个点解释一下，-5是正序遍历，也就是在100000点的左侧，在靠近这个点的999995这个位置上存上7.其它位置认为负无穷。接着是8，逆序遍历，在100008位置不会是1，因为100000位置是0，-6+0还是-6.当到了100003时，存1的值。所以只有smart相加为正时，才会出现在右侧。接下来我们只要在找在右侧的正数即可。你有没有在上面的信息中发现一个很重要的点呢？那就是j-100000就是j这个点所有smart的和，是不是很神奇。自己可以好好想想明白（相当于存字节长度）。

for (int j = maxnv; j <= maxnv*2; j++)
    if (dp[j] > 0)
        ans = max(ans, dp[j] + j - maxnv);

View Code

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define maxn 110
#define maxnv 110*1000
using namespace std;
int dp[maxnv * 2];

struct  Cow
{
    int sm, fu;
}cow[maxn];

int main()
{
    freopen("in.txt", "r", stdin);
    int n;
    while (~scanf("%d", &n))
    {
        memset(cow, 0, sizeof(cow));
        for (int i = 1; i <= n; i++)
            scanf("%d %d", &cow[i].sm, &cow[i].fu);
        for (int i = 0; i <= maxnv * 2; i++)
            dp[i] = -9999999;
        dp[maxnv] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (cow[i].sm > 0)
            {
                for (int j = maxnv * 2; j >= cow[i].sm; j--)
                    dp[j] = max(dp[j], dp[j - cow[i].sm] + cow[i].fu);
            }
            else
            {
                for (int j = 0; j - cow[i].sm <= maxnv * 2; j++)
                    dp[j] = max(dp[j], dp[j - cow[i].sm] + cow[i].fu);
            }
        }
        int ans = 0;
        for (int j = maxnv; j <= maxnv*2; j++)
            if (dp[j] > 0)
            {
                printf("dp[%d]=%d--%d
", j, dp[j], j - maxnv);
                ans = max(ans, dp[j] + j - maxnv);
            }
        printf("%d
", ans);
    }
    return 0;
}

View Code