王道机试指南 例题12.9 珍惜现在，感恩生活

题目：

算法梳理：

这题是“背包问题”的扩展，即“多重背包问题”。

• 多重背包问题

代码：

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int t;
    cin>>t;
    for(int k=0;k<t;k++){
        int m,n0;
        cin>>m>>n0;
        int w0[n0],v0[n0],c0[n0];
        for(int i=0;i<n0;i++)
            cin>>w0[i]>>v0[i]>>c0[i];

        //将k重背包问题转化为0-1背包问题
        vector<int> w,v;
        for(int i=0;i<n0;i++)
            for(int j=0;j<c0[i];j++){
                w.push_back(w0[i]);
                v.push_back(v0[i]);
            }
        int n=w.size();//更新物品件数

        int dp[m+1];
        for(int j=0;j<=m;j++)//初始化dp
            dp[j]=0;

        for(int i=0;i<n;i++)
            for(int j=m;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//状态转移方程

        cout<<dp[m]<<endl;
    }
    return 0;
}

运行结果：