请大家点个赞，有写的不好的可以在评论区评论

题目描述

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

第 $i$ 种物品最多有 $s_{i}$ 件，每件体积是 $v_{i}$，价值是 $w_{i}$。

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

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

接下来有 $N$ 行，每行三个整数 $v_{i},w_{i},s_{i}$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

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

数据范围
$0<N≤1000$
$0<V≤2000$
$0<v_{i},w_{i},s_{i}≤2000$

样例

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

分析

首先，我们要知道一个东西：
我们构造 $2^0 , 2^1 ,2^2 , … ，2^n$ 这个序列，能构造出 $1$ 到 $2^{n+1} -1$ 的所有数

相信大家都会，如果不会的话也没啥关系?(

所以我们可以死拆：
若这个东西有$n$件，我们可以拆成上面的序列，多出来的单独绑一块计算
(可以证明，多出来的一定小于拆出来的所有和，所以绑一起不会对答案有影响，相当于还是把多重背包拆成01背包，只是拆出来的是捆在一起计算的物品，我们可以简单的理解为一件物品)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,t,a,b,c,w[20005],v[20005],f[2005],cnt=0;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        int k=1;
        while(k<=c)
        {
            v[++cnt]=a*k;w[cnt]=b*k;
            c-=k;k*=2;
        }
        if(c>0){v[++cnt]=a*c;w[cnt]=b*c;}
    }
    for(int i=1;i<=cnt;i++)
    for(int j=t;j>=v[i];j--)
    f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[t];
}

2022.11.17 18:46 变得更短了（

saber简化代码

欢迎挑战更短(压行不算，我暂时没想出来更短的)

#include <bits/stdc++.h>
using namespace std;
int n,t,a,b,c,v,w,f[2005];
int main()
{
    cin>>n>>t;
    while(n--)
    {
        cin>>a>>b>>c;
        for(int k=1;c>0;c-=k,k*=2)
        {
            v=a*min(k,c);w=b*min(k,c);
            for(int j=t;j>=v;j--)f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[t];
}