[数据结构与算法]动态规划多重背包一维

多重背包问题朴素版（一维）

有 NN 种物品和一个容量是 VV 的背包。

第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i ++)//从小到大枚举个数
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for(int j = m; j >= v; j --)//从大到小枚举背包体积
            for(int k = 0; k <= s && k * v <= j; k ++)//从小到大枚举物品个数
                f[j] = max(f[j], f[j - k * v] + w * k);
    }
    
    printf("%d", f[m]);
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; i ++)//从小到大枚举个数 从0开始也可以
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for(int j = m; j >= v; j --)//从大到小枚举背包体积
            for(int k = 0; k <= s && k * v <= j; k ++)//从小到大枚举物品个数
                f[j] = max(f[j], f[j - k * v] + w * k);
    }
    
    printf("%d", f[m]);
    
    return 0;
}

做法：第一维遍历从小到大物品个数，从0或者1开始都可以；第二维从大到小遍历背包体积；第三维从小到大遍历物品个数。