头歌实训作业 算法设计与分析-动态规划(第1关：0/1背包问题)

任务描述

求解0/1背包问题。

问题描述

   有n个重量分别为{w 1，w 2，…，w n }的物品，它们的价值分别为{v 1，v 2 ，…，v n}，给定一个容量为 W 的背包。
  设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且重量和为 W ，并具有最大的价值。

测试说明

测试输入：
第一行为2个整数，分别表示物品数量 n（1≤n≤20） 和背包容量 W（1≤W≤10000） 。
接下来有2行，第一行表示n件物品的重量 w i（1≤w i ≤500），第二行表示n件物品的价值 v i 。

3 30
16 15 15
45 25 25

预期输出（最大价值）：
50

输出解释：
最大价值装入方案选第2件、第3件物品，重量=15+15=30，不超过载重限制，价值=25+25=50。

注意算法的时间复杂度优化，避免在物品数量较多时出现评测超时。

补充代码： 

 #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义背包问题函数
int knapsack(int n, int W, vector<int>& weights, vector<int>& values) {
    // 初始化DP数组
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // 填充DP数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (weights[i - 1] <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][W];
}

int main() {
    int n, W;
    // 输入物品数量和背包容量
    cin >> n >> W;

    vector<int> weights(n);
    vector<int> values(n);

    // 输入物品的重量
    for (int i = 0; i < n; ++i) {
        cin >> weights[i];
    }

    // 输入物品的价值
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }

    // 计算最大价值
    int max_value = knapsack(n, W, weights, values);
    cout << max_value << endl;

    return 0;
}