Atcoder DP Contest pD

題敘

https://atcoder.jp/contests/dp/tasks/dp_d
有一個負重上限為 $w$ 的背包
有 $n$ 個物品，每個物品都有其重量及價值
求能放入背包內的最大價值為何

想法

對於每個物品查看用該物品能組出的重量分別能形成的價值為多少並不斷更新
定義 $DP[i][j]$ 表示在前 $i$ 物中最大負重為 $j$ 時的最大價值
則可得轉移式 $DP[i][j] = max(DP[i-1][j], DP[i-1][j-cost[i]]+value[i])$
且為了避免取同物品多次的狀況，最大負重從 $w$ 開始往下算
不過在實作上可以發現到每次取的都是 $i-1$ 的狀態，所以實際上可以壓縮成一維

Code

//By Koios1143
#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,MaxW = 100005;
int n,w,cost[MaxN],value[MaxN];
long long dp[MaxW];
int main(){
	IOS
	while(cin>>n>>w){
		for(int i=0 ; i<n ; i++){
			cin>>cost[i]>>value[i];
		}
		for(int i=0 ; i<n ; i++){
			for(int j=w ; j-cost[i]>=0 ; j--){
				dp[j] = max(dp[j], dp[j-cost[i]]+value[i]);
			}
		}
		cout<<dp[w]<<"\n";
	}
	return 0;
}

複雜度

有 $w$ 種狀態，每種狀態轉移複雜度為 $O(n)$
總複雜度 $O(wn)$