带体积的背包问题c++

背包问题是一个经典的动态规划问题，其中背包有一定的容量，物品有不同的体积和价值。目标是在不超过背包容量的情况下，使得放入背包的物品总价值最大化。

下面是一个用C++实现的带体积的背包问题的代码示例：

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

using namespace std;

int knapsack(int capacity, vector<int>& volumes, vector<int>& values, int n)
{
    // 创建一个二维数组来保存动态规划的结果
    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 (volumes[i-1] <= j)
            {
                // 当前物品的体积小于等于背包容量时，可以选择放入或不放入背包
                dp[i][j] = max(values[i-1] + dp[i-1][j-volumes[i-1]], dp[i-1][j]);
            }
            else
            {
                // 当前物品的体积大于背包容量时，只能选择不放入背包
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return dp[n][capacity];
}

int main()
{
    int capacity = 10;  // 背包容量
    vector<int> volumes = {2, 3, 4, 5};  // 物品的体积
    vector<int> values = {3, 4, 5, 6};  // 物品的价值
    int n = volumes.size();  // 物品的数量
    
    int maxValue = knapsack(capacity, volumes, values, n);
    
    cout << "最大价值为: " << maxValue << endl;

    return 0;
}

这段代码使用动态规划的思想，通过填充一个二维数组 `dp` 来解决背包问题。其中 `dp[i][j]` 表示在前 `i` 个物品中，背包容量为 `j` 的情况下，可以获得的最大价值。最终返回 `dp[n][capacity]` 即可得到结果。

注意，这段代码假设物品的体积和价值已经按照相同的顺序存储在 `volumes` 和 `values` 向量中，并且索引从0开始。