算法简单背包问题的代码c++

算法简单背包问题通常是指0-1背包问题（Knapsack Problem），它是一个经典的动态规划问题。以下是使用C++编写的简单背包问题的代码示例：

#include <iostream>
#include <vector>

using namespace std;

int knapSack(int W, vector<int>& wt, vector<int>& val, int n) {
    // 创建一个二维数组来存储子问题的解
    vector<vector<int>> dp(n + 1, vector<int>(W + 1));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                // 如果物品能完全放入背包，取价值最大的
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
            } else {
                // 如果物品太大，就只能选择不放
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W]; // 返回最大总价值
}

int main() {
    int weight_capacity = 50;
    vector<int> weights = {10, 20, 30}; // 物品重量
    vector<int> values = {60, 100, 120}; // 物品价值
    int num_items = weights.size();

    cout << "Max value in the knapsack is: " << knapSack(weight_capacity, weights, values, num_items) << endl;

    return 0;
}

这个代码首先初始化了一个动态规划表格`dp`，然后通过嵌套循环遍历每个物品和背包容量的情况，根据物品是否能装入背包，决定是否选择当前物品。最后返回整个背包所能达到的最大价值。