一、問題闡述
0-1 背包問題的目標是在給定背包容量?W?的情況下，從?n?個物品中選擇一些物品放入背包，使得背包中物品的總價值最大。每個物品只能選擇一次（即要么放入背包，要么不放入）。
二、代碼
#include <iostream>
#include <vector>
using namespace std;// 動態規劃解決 0-1 背包問題
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {// 創建二維 DP 表vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));// 填充 DP 表for (int i = 1; i <= n; ++i) {for (int w = 0; w <= W; ++w) {if (weights[i - 1] <= w) {// 選擇第 i 個物品dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {// 不選擇第 i 個物品dp[i][w] = dp[i - 1][w];}}}// 返回最大價值return dp[n][W];
}int main() {// 輸入int n, W;cout << "請輸入物品數量 n 和背包的最大承重 W: ";cin >> n >> W;vector<int> weights(n);vector<int> values(n);cout << "請輸入每個物品的重量: ";for (int i = 0; i < n; ++i) {cin >> weights[i];}cout << "請輸入每個物品的價值: ";for (int i = 0; i < n; ++i) {cin >> values[i];}// 計算最大價值int max_value = knapsack(W, weights, values, n);// 輸出結果cout << "最大總價值為: " << max_value << endl;return 0;
}
三、復雜度
-
時間復雜度：
O(n * W)，其中?n?是物品數量，W?是背包容量。 -
空間復雜度：
O(n * W)，用于存儲 DP 表。
四、詳細闡述
代碼結構
-
輸入部分：從用戶那里獲取物品數量?
n、背包容量?W，以及每個物品的重量和價值。 -
動態規劃求解：使用二維 DP 表來存儲子問題的解，逐步填充表格，最終得到最大價值。
-
輸出部分：輸出背包能容納的最大價值。
動態規劃表?dp
-
dp[i][w]?表示前?i?個物品在背包容量為?w?時的最大價值。 -
dp?表的大小為?(n + 1) x (W + 1)，初始化為 0。
狀態轉移方程
-
對于第?
i?個物品，有兩種選擇：-
不選擇第?
i?個物品：最大價值為?dp[i - 1][w]。 -
選擇第?
i?個物品：最大價值為?dp[i - 1][w - weights[i - 1]] + values[i - 1]。
-
-
最終選擇兩者中的最大值
)
