#include <iostream>
#include <vector>
using namespace std;
<p>int knapsack(int W, vector<int>& weight, vector<int>& value) {
int n = weight.size();
// 创建二维DP表
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));</p><pre class='brush:php;toolbar:false;'>// 填充DP表
for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        // 不选第i个物品
        dp[i][w] = dp[i-1][w];
        // 如果能装下第i个物品，尝试选择它
        if (weight[i-1] <= w) {
            dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
        }
    }
}

return dp[n][W];

}

int main() { vector value = {60, 100, 120}; vector weight = {10, 20, 30}; int W = 50; cout

int knapsack_optimized(int W, vector<int>& weight, vector<int>& value) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);
<pre class='brush:php;toolbar:false;'>for (int i = 0; i < n; i++) {
    // 从后往前更新，防止重复使用
    for (int w = W; w >= weight[i]; w--) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}
return dp[W];

}