AcWing 1019. 庆功会【多重背包问题 + DP 】题解

左手的ㄟ右手 2021-07-24 18:56 487阅读 0赞

> hello大家好，欢迎大家访问 林深时不见鹿 的博客，算法小白，记录学习的点滴日常，致力于通俗易懂的题解，相遇即是上上签，如有不足，还请多多指教。  
> 
> 
> ### 目录 ###
> 
>  *   *   *  AcWing 1019. 庆功会
>          *  思路
>          *  代码

### AcWing 1019. 庆功会 ###

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

**输入格式**  
第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。

**输出格式**  
一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

**数据范围**  
n≤500,m≤6000,  
v≤100,w≤1000,s≤10  
**输入样例：**  
5 1000  
80 20 4  
40 50 9  
30 50 7  
40 30 6  
20 20 1  
**输出样例：**  
1040

### 思路 ###

*  **多重背包问题：每种物品可用s次**
 *  背包的总体积V: 拨款金额m
 *  物品的种数N：奖品的种数n
 *  每种物品的价值w：该奖品的价值
 *  每种物品的体积v：该奖品的价格  
    状态表示：`f[i][j]`：只从前i个物品中选，且总体积不超过j的所有选法集合的最大值  
    状态计算：`f[i][j]=max(f[i][j],f[i-1][j-k*v]+k*w)`  
    在能装下的情况下每种物品可以选0次，1次，2次，，，k次  
    由于数据范围较小，所以不需要进行二进制，或单调队列优化  
    时间复杂度 O(nms) 大约为 3e7  
    这里将二维优化到了一维。

### 代码 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N=6010;
    int f[N];
    int main()
    { 
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        { 
            int v,w,s;
            cin>>v>>w>>s;
            for(int j=m;j>=v;j--)
            { 
                for(int k=0;k<=s&&k*v<=j;k++)
                { 
                    f[j]=max(f[j],f[j-k*v]+k*w);
                }
            }
        }
        cout<<f[m]<<endl;
        return 0;
    }