問題

這邊一樣以 AtCoder Educational DP Contest 的類題來舉例，這題是 D - Knapsack 1，題意大概是有一個背包，裡面只能放重量 的東西，接下來有 個物品，每個物品都有價值與重量，現在要求可以放入背包物品的最大價值總和是多少，有個重點是物品皆不可以分割

解題思路

由於最多只能裝 且商品不可分割，所以不可以用 greedy 的方式來選擇商品，那試著思考看看，如果建一張 的表，枚舉重量由 ~ 可以裝多少商品，且計算最高價值，然後歸納一個式子是，簡單來說是因為如果 j - w[i] >= 0 就代表裝的下此物品，所以就可以確認再裝物品下去會不會比較好或是直接沿用之前的裝填方式就可以了，只要不斷照著這步驟做就可以取得最高價值了

AC Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,W;
    cin >> n >> W;
    vector<long long> w(n + 1),v(n + 1);
    for(int i = 1;i <= n;i++){
    	cin >> w[i] >> v[i];
    }
    vector<vector<long long>> dp(n + 1,vector<long long>(W + 1,0));
    for(int i = 1;i <= n;i++){
    	for(int j = 1;j <= W;j++){
    		if(j - w[i] >= 0){
    			dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]);
    		}else{
    			dp[i][j] = dp[i - 1][j];
    		}
    	}
    }
    cout << dp[n][W] << "\n";
    return 0;
}

時間複雜度

由於需要遍歷物品及枚舉各個重量，所以時間複雜度是

總結

今天的內容比較不好理解一些，不過背包問題可能會有變形的題目出現在比賽中，所以也是要好好理解並且練習思考