Thoughts on a "01 knapsack problem" expansion problem

[USACO03FALL]Cow Exhibition G

Background

Title Description

Cows want to prove that they are smart and funny . So , Bessie set up a dairy Fair , She has been right $N$ A cow had an interview , The IQ and EQ of each cow were determined .

Bessie has the right to choose which cows to show . Because negative IQ or EQ can have negative effects , So Bessie doesn't want to show that the sum of cows' IQ is less than zero , Or the sum of EQ is less than zero . Under these two conditions , She hopes to show that the greater the sum of IQ and EQ of cows, the better , Please help Bessie find this maximum .

Input format

first line ： A single integer $N$,$1\le N\le 400$.

Line two to line two $N+1$ That's ok ： The first $i+1$ Line has two integers ：$S_i$ and $F_i$, It means the first one $i$ The IQ and EQ of a cow ,− $1000\le S_i;F_i\le 1000$.

Output format

Output a single integer ： Indicates the maximum sum of EQ and IQ . Bessie can exclude any cows from the exhibition , If this is the best , Output $0$.

Examples #1

The sample input #1

5
-5 7
8 -6
6 -3
2 1
-8 -5

Sample output #1

8

Tips

Select the first end , The third end , The fourth cow , IQ and −5+6+2 = 3, EQ and Wei 7−3+1 = 5. add

Entering the second cow can increase the total to 10, However, because of emotional intelligence and become negative , So it's not allowed

 The question is 01 An extension of knapsack problem , It's hard to think of , Regard IQ as volume , Emotional intelligence as value ,
 Because IQ is negative , According to the data, the sum of IQ can be calculated : -400*1000 <= sum <= 400 * 1000,.
 So you can add an offset to your IQ 400*1000, In this way, as an array subscript, it will not be out of bounds 

Draw the key : This question should be guaranteed dp[j] Is just IQ and for j-M, How do you guarantee that ？ This is how the following code initializes all values to -0x3f3f3f3f, Double this number will not overflow , Then initialize f[M]=0, In this way, we finally get max The maximum values in are those from 0 Shift from the past , That is, it happens to go through many iterations dp[j] = max(dp[j], dp[j - s[i]] + f[i]); The source of the final maximum value is from dp[M] That is, IQ and for 0 Transfer the past , This ensures our final result dp[j] It must be just IQ and for j-M
Ideas refer to : Backpack problem review list explanation
The code is as follows :

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10, M = 400 * 1000;

int dp[N], n, s[N], f[N];

int main()
{
    
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> s[i] >> f[i];
    memset(dp, -0x3f, sizeof dp);// Because EQ is negative , take max, To initialize negative infinity 
    dp[M] = 0;// These two lines guarantee dp[j] Is just IQ and for j-M
    for(int i = 0; i < n; i ++){
    
   		// Yes 01 Backpack has been expanded , because j - s[i] May be greater than j It may also be less than j
   		// One dimensional processing , the truth is that dp[i][j], Once upon a time i Among them, the IQ is only j-M The greatest emotional intelligence selected 
   		// So if j - s[i] Greater than j It is necessary to traverse the update in positive order , Because it is used behind the upper floor 
   		// If j - s[i] Less than j It is necessary to traverse the update in reverse order , Because it uses the one in front of the upper floor 
        if(s[i] >= 0)
            for(int j = 2 * M; j >= s[i]; j --)
                dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
        else
            for(int j = 0; j <= s[i] + 2 * M; j ++)
                dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
    }
    int  res = 0;
    for(int i = M; i <= 2 * M; i ++)
        if(dp[i] > 0)
            res = max(res, dp[i] + i - M);
    cout << res << endl;
    return 0;
}