SMRTFUN

題目大意：

有n件物品，每件物品有各自的a值和b值，現在讓你選一些物品，在a、b都不是負數的情況下，使a、b值之和最大

輸入樣例

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

輸出樣例

8

樣例說明

選擇第1，3和4號牛。TS=-5+6+2=3，TF=7-3+1=5，所以，TS+TF=3+5=8。雖然，加上2號牛可以使總和變成10，但是，TF小于0，不符合要求。

數據范圍

$1?N?100$
$?1000?S_i?1000$
$?1000?F_i?1000$
時間限制：$3000MS$

解題思路：

一開始我們會想到二維背包，但這樣回TLE
我們看到背包里面存的數就01會十分浪費，就把第二維放進去計算，這樣就省去了一維

代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,a,b,ans,f[202000]; int main() {scanf("%d",&n);memset(f,-127/3,sizeof(f));f[100100]=0;for (int i=1;i<=n;++i){scanf("%d %d",&a,&b);if (a<0)//分兩種情況for (int j=1;j<=200200+a;++j)//a是負數時要倒著f[j]=max(f[j],f[j-a]+b);//DPelsefor (int j=200200;j>=a;--j)f[j]=max(f[j],f[j-a]+b);}ans=-2147483647;for (int i=100100;i<=200200;++i)if (f[i]>=0)ans=max(ans,f[i]+i-100100);//求一個最優的printf("%d",ans); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【背包】SMRTFUN的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。