假设一背包承重为10斤，怎样放入水果使得背包中的价值最大c++

要在 C++ 中解决这个问题，通常会采用动态规划算法，特别是贪心算法的一种变种，称为“0-1 包装问题”或“knapsack problem”。这是一个经典的优化问题，假设我们有 n 个水果，每个水果 i 都有一个重量 w_i 和一个价值 v_i。目标是在不超过背包总重量的前提下，选择一些水果组合，使其总价值最大。

以下是简单的思路：

1. 定义两个数组：`weights` 存储水果重量，`values` 存储水果价值。
2. 创建一个二维动态规划数组 `dp`，其中 `dp[i][j]` 表示前 i 个水果中选择重量不超过 j 的情况下能得到的最大价值。
3. 使用双重循环，对于每个水果 i 和背包剩余容量 j，判断是否应该包含当前水果（即 `weights[i] <= j`），如果不包含，则 `dp[i][j] = dp[i - 1][j]`；如果包含，那么可以更新 `dp[i][j]` 为包含当前水果后的价值 `dp[i - 1][j - weights[i]] + values[i]`，取两者中的较大值。
4. 最终，`dp[n][10]` 就是背包能承载的10斤内所能达到的最大价值。

下面是一个简单的 C++ 示例代码：

#include <iostream>
#include <vector>

int knapSack(int W, std::vector<int>& weights, std::vector<int>& values, int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i-1] <= w) {
                dp[i][w] = std::max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    std::vector<int> weights = {1, 3, 4, 5};
    std::vector<int> values = {1, 4, 5, 7};
    int W = 10;
    int n = weights.size();
    int max_value = knapSack(W, weights, values, n);
    std::cout << "背包中的最大价值为: " << max_value << std::endl;
    return 0;
}