---
# System prepended metadata

title: 0-1 背包(一維)

---

有 $N$ 個物品，第 $i$ 個物品重量為 $w_i$，價值為 $v_i$，背包容量為$W$，求背包內物品的最大價值總和 $(N \le 100,\,w_i \le W \le 10^5,\,v_i \le 10^9\,)$。
* DP 定義：
	* $dp[\,j\,]$：當前背包重量為 $j$ 時的最大價值和
* 找出轉移式：
	* 考慮前 $i-1$ 個物品的取捨，當前重量和為 $j$
	* 第 $i$ 個商品選擇取或不取
		* 取：$dp[\,j\,]=dp[\,j-w[\,i\,]\,]+v[\,i\,]$
		* 不取：$dp[\,j\,]$ 維持不變
	* 轉移式：$dp[\,j\,]=\max(dp[\,j\,],\,dp[\,j-w[\,i\,]\,]+v[\,i\,])$
```cpp
void sol(){
    cin >> N >> W ;
    for(int i = 1; i <= N; i ++)
        cin >> w[i] ;
    for(int i = 1; i <= N; i ++)
        cin >> v[i] ;
    for(int i = 1; i <= N; i ++)
    // 先遍歷物品：因為是對物品選擇取或不取來決定重量
        for(int j = W; j >= w[i]; j --)
        // j >= w[i]：若 w[i] > j 顯然放不下
        // 重量(j)由大到小遍歷：因為每個物品只能取一次，這樣是為了確保 dp[j] 是由 dp[j - w[i]] 推得
            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
    cout << dp[W] << "\n" ;
}
```