多重背包问题【多重背包】【最基础的板子】【动态规划】

#include<iostream>
using namespace std;
const int MAXN =1100;

int w[MAXN];
int v[MAXN];
int main()
{
    int n,m;
    cin>>n>>m;
    int number =1;//为了打表时候第一个物品下标是1
    v[0]=w[0]=0;
    while(n--)
    {
        int weight;
        int value;
        int k;
        cin>>weight>>value>>k;
        //二进制拆分
        for(int j=1; j<=k; j<<=1)
        {
            w[number]=j*weight;
            v[number]=j*value;
            number++;
            k-=j;
        }
        //此时的k很小了，与前面的所有出现过的j求和就是原来的k，并且这个组合 可以表示[0,原来k]数量   这就是二进制分解的妙处，还降低了时间复杂度
        if(k)
        {
            w[number]=k*weight;
            v[number]=k*value;
            number++;
        }
    }

    int dp[MAXN][110];

    // 0-1 背包打表
    for(int i=0; i<number; i++)//这里0开始，是初始化和状态计算同时进行
    {
        for(int j=0; j<=m; j++)
        {
            if(i==0||j==0)
            {
                dp[i][j]=0;
                continue;
            }

            dp[i][j]=dp[i-1][j];
            if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
    cout<<dp[number-1][m]<<endl;

}