题目描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

算法

(看做0/1背包问题的变种)

在0/1背包问题中我们对于每个物品都做一个判断，取或者不取。
本题中对该问题进行了拓展，但是核心思想不变。我们可以将 每种物品分成单个物品，对第i种物品判断$s_i$次，对于 每个物品 进行判断取或者不取，将题目转换为0/1背包问题。

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 110;
int n, v;
int tempv, tempw, temps;
int dp[M];
int main()
{
    cin >> n >> v;
    for(int i=0; i<n; i++)
    {
        cin >> tempv >> tempw >> temps;
        while(temps--)
            for(int j=v; j>=tempv; j--)
            {
                dp[j] = max(dp[j], dp[j-tempv] + tempw);
            }
    }
    cout << dp[v];
    return 0;
}