当前位置: 代码迷 >> 综合 >> DP 多重背包 庆功会
  详细解决方案

DP 多重背包 庆功会

热度:29   发布时间:2024-01-15 08:45:27.0

庆功会

【题目描述】

为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品,可以补充他们的精力和体力。

【输入】

第一行二个数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;
}

  相关解决方案