POJ 2184 Cow Exhibition(0-1 백팩)

제목 설명: Cow Exhibition Time Limit: 1000MS Memory Limit: 65536K
“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 5 -5 7 8 -6 6 -3 2 1 -8 -5
Sample Output 8
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.
제목 대의: 우선 제목의 대의는 매우 간단하다. 바로 한 농부가 n마리의 소를 가지고 가려고 한다. 그는 소를 좀 데리고 가려고 한다. 그래서 이 소들의 t와 f의 것이 가장 크고 t의 것과 f의 것이 모두 마이너스이다.
제목 분석: 0-1배낭, 전통적인 0-1배낭은 개체마다 두 가지 속성이 있는데 이것도 마이너스 값만 있는 존재이기 때문에 그 중의 한 속성을 무게로 볼 수 있다. 다른 하나는 가치로 볼 수 있다. 우리는 dp[i][j]: 앞의 i마리 소, t의 것과 j를 위한 f의 합의 최대치는 t의 합과 최소가 -100000이고 최대는 100000이다.그래서 우리는 2차원 전체 +100000(이것은 게으름을 피우는 방법일 뿐이고 n의 규모에 따라 크기를 조정할 수도 있다. 이렇게 하면 공간을 절약할 수 있다)이 된다. 그러면 dp[100][200000]이 된다. 이때 0~20000000은 각각 -10000~100000으로 비추고 i두 번째 소의 t>=0이 되면 일반적인 0-1배낭이다. 이때 dp[i]=max(dp[i][j], dp[i-1][coj-[i].s+cowi], 이 방정식을 보면 이 상태로 이동한다.매번 dp[i][j]를 업데이트할 때마다 원시치와 제 i마리 소를 추가하지 않았을 때 대응하는 j-j-cow[i]를 사용합니다.s곳(j보다 작은)의 값을 갱신하면 우리는 비례를 낮출 수 있다. j의 최대치부터 다시 갱신할 수 있다. 이렇게 필요한 두 값은 현재의 dp수조에서 찾을 수 있다. (전 왕후의 경우 비례가 낮아진 후 j-j-cow[i].s의 값은 이미 i두소를 넣은 결과로 갱신되었다) 같은 이치이다. i두소에 대응하는 t<0시,j는 어릴 때부터 큰 값으로 업데이트하면 된다. 초치: 마이너스의 존재 최대치가 마이너스일 수 있기 때문에 dp수조를 업데이트할 때 -INF를 사용해야 한다. 물론 소 한 마리를 선택하지 않을 때 f와 최대치가 0이고 비추면 dp[100000]=0이다.코드:

#include "stdio.h"
#include "algorithm"
#define INF 1e8
using namespace std;
int n;
struct node
{
    int s,f;
};
node cow[100+5];
int dp[200000+5];
int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&cow[i].s,&cow[i].f);
        }
        fill(dp,dp+200000+5,-INF);
        dp[100000]=0;
        for(i=1;i<=n;i++)
        {
            if(cow[i].s>=0){
            //      
                for(j=200000;j>=cow[i].s;j--)
                {
                    dp[j]=max(dp[j],dp[j-cow[i].s]+cow[i].f);
                }
            }else{
            //      
                for(j=0;j-cow[i].s<=200000;j++)
                {
                    dp[j]=max(dp[j],dp[j-cow[i].s]+cow[i].f);
                }
            }

        }
        int mx=0;
        for(i=100000;i<=200000;i++)
        {
            if(dp[i]>=0)
                mx=max(mx,dp[i]+i-100000);
        }
        printf("%d
",mx);

    }
    return 0;
}