本文主要是介绍DP 多重背包 庆功会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
庆功会
【题目描述】
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入】
第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中v≤100，w≤1000，s≤10。
【输出】
一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
【输入样例】
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
【输出样例】
1040
【来源】
No
算法分析：
多重背包问题，介绍两种算法朴素算法和二进制优化算法。
朴素算法：
可以转化为01背包问题，即第i种物品有s[i]件，
则状态转移方程为：f[i][m]=max(f[i-1)[m],f[i][m-k*v[i]]+k*w[i])0<=k<=s[i];
实现代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{int n,m,i,k,j,f[6002]={0};int v[6002],s[6002],w[6002];cin>>n>>m;for(i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];for(i=1;i<=n;i++)for(j=m;j>=0;j--)for(k=0;k<=s[i];k++){if(j-k*v[i]<0) break;f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}cout<<f[m];return 0;
}
第二种方法：
将第i种物品分成若干件物品，就是把它分成好几堆，其中每件物品都有一个系数，zhe堆物品的费用和价值是原来的费用和价值乘以所对应的系数，精华来了：这些系数为 1，2，4，……2的（k-1）次方，s[i]-2的k次方+1。s[i]-2的k次方+1必须大于0。拿一个实例，假如是s[i]=13,则系数为1，2，4，6。你会发现这些系数能组合1~s[i]所有的数。
代码实现：
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m,i,k,j,f[6002]={0};int v[6002],s[6002],w[6002];cin>>n>>m;int nl=0;for(i=1;i<=n;i++){int x,y,s,t=1;cin>>x>>y>>s;while(s>=t) //转化为二进制，实现系数{nl++;v[nl]=t*x;w[nl]=t*y;s-=t;t*=2;}nl++;v[nl]=s*x;w[nl]=s*y;}for(i=1;i<=nl;i++)for(j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m];return 0;
}
这篇关于DP 多重背包 庆功会的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
