Atcoder DP Contest pE
題敘
https://atcoder.jp/contests/dp/tasks/dp_e
與pD相同,但是重量可以來到 $10^9$
問最大價值
想法
因為重量太大了,導致無法使用pD的作法
但是價值不大,可以從這裡下手
將問題倒過來思考,如果知道在某價值下最小的重量總和,那麼只要重量總和小於等於題目要求,那麼該價值的最大值即為解
定義 $DP[i]$ 表示在價值為 $i$ 時的最小重量總和
則有轉移式 $DP[i] = min(dp[i], dp[i-value[j]]+cost[j])$
且已知 $dp[0] = 0$
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<bits/stdc++.h> #define LL long long #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define pii pair<int,int> using namespace std; const int MaxN = 105,MaxV = 100005; int n,w,cost[MaxN],value[MaxN]; long long dp[MaxV]; int main(){ IOS while(cin>>n>>w){ int tot_value=0; for(int i=0 ; i<n ; i++){ cin>>cost[i]>>value[i]; tot_value+=value[i]; } for(int i=1 ; i<=tot_value ; i++){ dp[i] = INT_MAX; } for(int i=0 ; i<n ; i++){ for(int j=tot_value ; j>=value[i] ; j--){ dp[j]=min(dp[j], dp[j-value[i]]+cost[i]); } } int ans=0; for(int i=tot_value ; i>0 ; i--){ if(dp[i]<=w){ ans=i; break; } } cout<<ans<<"\n"; } return 0; }
|
複雜度
有 $NV$ 種狀態,每種狀態轉移複雜度為 $O(1)$
輸出複雜度也為 $O(NV)$
總複雜度 $O(NV)$