使用一维数组进行滚动优化，降低空间复杂度

1. 创建一维数组 f[j]：我们使用一维数组来保存背包容量为 j 时的最大价值。这样可以减少空间的使用，因为我们只需要保存当前行和上一行的状态信息，而不需要保存整个二维数组。

2. 初始化一维数组 f[j] 为 0：在还没有考虑任何物品放入背包时，最大价值都是 0。通过将一维数组初始化为 0，我们确保初始状态下没有物品放入背包时的最大价值都为 0。

3. 从大到小遍历背包容量 j 和物品 i：这里的遍历顺序是从大到小，是为了保证在计算当前物品 i 时，前面的物品 i-1 的值没有被修改。这样可以保证我们在计算当前行的值时，所依赖的上一行的值是正确的。

4. 判断当前物品是否可以放入背包：我们通过比较当前物品 i 的体积 v[i] 和背包容量 j 来判断是否可以放入背包。只有当 v[i] <= j 时，当前物品才可以放入背包中。

5. 更新 f[j] 的值：对于每个物品 i，我们有两种选择：放入或不放入。如果选择放入，那么当前的最大价值为 f[j-v[i]] + w[i]，表示在背包容量为 j-v[i] 时选择放入当前物品 i 的最大价值，并加上当前物品的价值 w[i]。如果选择不放入，那么当前的最大价值为 f[j]，表示在背包容量为 j 时选择不放入当前物品 i 的最大价值。我们通过比较这两种情况的值，选择较大的那个来更新 f[j] 的值。这样，我们就得到了当前行的最大价值。

6. 遍历完所有物品后，f[V] 即为背包容量为 V 时的最大价值：通过遍历所有物品，并根据背包容量和物品的选择来更新 f[j] 的值，我们最终得到了背包容量为 V 时的最大价值。

通过这些步骤，我们可以使用一维数组进行滚动优化，减少了空间的使用，并保证了计算最大价值的正确性。

#include <bits/stdc++.h>
using namespace std;

const int MAX = 110;
int v[MAX], w[MAX], s[MAX], f[MAX];

int main()
{
    int N, V;
    cin >> N >> V;  // 输入物品种类数和背包容量

    // 输入物品信息
    for (int i = 1; i <= N; i++)
    {
        cin >> v[i] >> w[i] >> s[i];  // 物品体积、价值和数量
    }

    // 多重背包问题求解
    for (int i = 1; i <= N; i++)
    {
        for (int j = V; j >= v[i]; j--)
        {
            for (int k = 0; k <= s[i] && k <= j / v[i]; k++)
            {
                // 对于第i种物品，考虑取0到s[i]个物品
                // 并计算取不同数量的物品时的最大价值
                f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << f[V] << endl;  // 输出最大价值
    return 0;
}

二进制拆分思想–二进制优化

当有50个苹果，并且要取n个苹果（n≤50）时，我们可以利用二进制拆分思想和箱子进行一些预备工作，以优化取苹果的过程。

首先，我们可以将每个箱子中放置的苹果数量进行二进制拆分。假设有6个箱子，我们可以拆分为1、2、4、8、16和19个苹果（剩余的数）

然后，我们可以将第i种物品（即第i个箱子）拆分成若干件物品。

通过这种拆分，我们将每个箱子中的苹果拆分为多个物品，每个物品的体积和价值都是箱子中苹果的体积和价值乘以拆分系数。

接下来，我们将问题转化为01背包问题。以si为例，假设拆分系数为1、2、4和5，我们可以将si拆分成4个01背包的物品：

• 物品1：体积为v，价值为w
• 物品2：体积为2v，价值为2w
• 物品3：体积为4v，价值为4w
• 物品4：体积为5v，价值为5w

现在，我们可以使用常规的01背包算法来求解这个问题。通过动态规划，我们可以计算出在取任意n个苹果时，所需的箱子数量。

通过这种优化，我们可以减少取苹果的时间复杂度，提高效率，并且可以利用01背包问题的解决方法来解决这个问题。

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e6 + 10;
int a, b, c, k, cnt;
int v[MAX], w[MAX], f[MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    cnt = 0;

    // 输入物品信息
    for (int i = 1; i <= N; i++)
    {
        cin >> a >> b >> c;
        k = 1;

        // 将物品拆分为二进制倍数
        while (k <= c)
        {
            v[++cnt] = k * a;  // 物品体积
            w[cnt] = k * b;   // 物品价值
            c -= k;
            k *= 2;
        }

        // 处理剩余的物品数量
        if (c)
        {
            v[++cnt] = c * a;  // 物品体积
            w[cnt] = c * b;   // 物品价值
        }
    }

    // 01背包算法求解
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = V; j >= v[i]; j--)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[V] << endl;  // 输出最大价值
    return 0;
}