1 //Accepted    1492 KB    110 ms 2 //背包 3 //把si看成weight，Fi看成value，这可以表示成当dp[j]=max(dp[j-weight[i]]+value[i]) 4 //考虑到si可能为负，需要整段区间的平移 5 //背包过程中，根据weight的正负，我们需要考虑dp的顺序，如果weight为正，这j从大到小 6 //如果weight为负，则要从小到大，这是根据dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i]) 7 //如果我们省略一维，这需要先更新j,再更新j-weight[i]，当weight[i]为正时，我们要先更新大的。。。 8 #include <cstdio> 9 #include <cstring>10 #include <iostream>11 #include <queue>12 #include <cmath>13 #include <algorithm>14 using namespace std;15 /**16   * This is a documentation comment block17   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！18   * @authr songt19   */20 const int inf = 100000000;21 const int imax_n = 105;22 int value[imax_n];23 int weight[imax_n];24 int dp[200005];25 int n;26 int max(int a,int b)27 {28     return a>b?a:b;29 }30 void Dp()31 {32     for (int i=0;i<=n*2000;i++) dp[i]=-inf;33     dp[n*1000]=0;34     for (int i=1;i<=n;i++)35     {36         if (value[i]<=0 && weight[i]<=0) continue;37         if (weight[i]>0)38         {39             for (int j=n*2000;j>=weight[i];j--)40             if (dp[j-weight[i]]>-inf)41             dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);42         }43         else44         {45             for (int j=0;j<=n*2000+weight[i];j++)46             if (dp[j-weight[i]]>-inf)47             dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);48         }49     }50     int ans=0;51     for (int i=n*1000;i<=n*2000;i++)52     if (dp[i]>=0)53     ans=max(ans,dp[i]+i-n*1000);54     printf("%d\n",ans);55 }56 int main()57 {58     while (scanf("%d",&n)!=EOF)59     {60         for (int i=1;i<=n;i++)61         scanf("%d%d",&weight[i],&value[i]);62         Dp();63     }64     return 0;65 }