贪心的零一背包c++

贪心的零一背包算法（0-1 Knapsack Problem）是一种经典的动态规划问题，用于解决物品分配问题，给定一组物品，每件物品有自己的重量和价值，目标是在不超过背包容量的前提下，选择总价值最大的物品组合。

在 C++ 中，可以采用迭代的方式来实现这个算法。以下是基本步骤：

1. 定义两个数组：`weights` 存储物品的重量，`values` 存储物品的价值。
2. 创建一个二维数组 `dp`，其中 `dp[i][w]` 表示在前 `i` 个物品中，能够获取的最大价值，同时背包总重量不超过 `w`。
3. 遍历每个物品 `i` 和背包剩余容量 `j`，有两种情况：
- 如果当前物品太重，无法放入背包 (`weights[i] > j`)，则直接复制上一个状态（`dp[i-1][j]`）；
- 否则，可以选择放（`dp[i-1][j] + values[i]`），也可以选择不放（`dp[i-1][j]`），取两者中价值更大的那一个作为新的状态 (`max(dp[i-1][j], dp[i-1][j-weight[i]] + values[i])`).
4. 当遍历完所有物品，`dp[n-1][W]` 就是最大价值，其中 `n` 是物品的数量，`W` 是背包的容量。

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