c++实现0-1背包问题动态规划法

0-1背包问题是经典的动态规划问题，可以使用c++来实现。以下是一种基于动态规划的解法：

#include <iostream>
#include <vector>
using namespace std;

int knapsack(vector<int>& values, vector<int>& weights, int capacity) {
    int n = values.size();
    vector<vector<int>> dp(n+1, vector<int>(capacity+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; 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][capacity];
}

int main() {
    vector<int> values = {6, 10, 12};
    vector<int> weights = {1, 2, 3};
    int capacity = 5;
    cout << knapsack(values, weights, capacity) << endl;
    return 0;
}

首先定义一个二维的dp数组，其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。在枚举每个物品时，分为两种情况：如果当前物品可以放入背包中，则需要考虑将其放入或不放入背包中所能获得的最大价值，即dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])；如果当前物品不能放入背包，则直接继承上一个物品的最大价值，即dp[i][j] = dp[i-1][j]。最后返回dp[n][capacity]即可。