多重背包朴素版,时间复杂度O(NVS)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;

int n,m;
int v[N],w[N],s[N];
int f[N][M];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> s[i];

     // 多重背包朴素版，时间复杂度O(NVS)
    for(int i=1;i<=n;i++) // 从前i个物品中选
    {
        for(int j =0;j<=m;j++) // 体积不超过j
        {
            for(int k =0; k<=s[i] && k * v[i] <= j;k ++) // 选多少个,限制1:数量s[i];限制2:体积k * v[i] <= j
            {
                f[i][j] = max(f[i][j],f[i-1][j-k * v[i]] + k * w[i]);
            }
        }
    }

    cout<<f[n][m]<<endl;

    return 0;
}

优化空间的写法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;

int n,m;
int v[N],w[N],s[N];
//int f[N][M];
int f[M];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> s[i];

     // 多重背包朴素版，时间复杂度O(NVS)
    for(int i=1;i<=n;i++) // 从前i个物品中选
    {
        for(int j =m;j>=0;j--) // 体积不超过j,体积从大到小循环
        {
            for(int k =0; k<=s[i] && k * v[i] <= j;k ++) // 选多少个,限制1:数量s[i];限制2:体积k * v[i] <= j
            {
                f[j] = max(f[j],f[j-k * v[i]] + k * w[i]);
            }
        }
    }

    cout<<f[m]<<endl;

    return 0;
}