01背包问题动态规划
01背包问题是一个经典的动态规划问题,在给定一定容量的背包和一组物品的情况下,求出装入背包的物品组合,使得总价值最大。
以下是一个用动态规划解决01背包问题的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 01背包问题的动态规划解法
int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
// 创建一个二维数组dp,其中dp[i][w]表示前i个物品放入容量为w的背包中所能获得的最大价值
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 动态规划求解
for (int i = 1; i <= n; ++i) {
for (int w = 1; w <= W; ++w) {
// 如果第