庆功会 Description 为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品,可以补充他们的精力和体力。 Input 第一行二个数n(n≤500),m(m≤6000),其中n代表希望购买的奖品的种数,m表示拨款金额。接下来n行,每行3个数,v、w、s,分别表示第I种奖品的价格、价值(价格与价值是不同的概念)和能购买的最大数量(买0件到s件均可),其中v≤100,w≤1000,s≤10。 Output 一行:一个数,表示此次购买能获得的最大的价值(注意!不是价格)。 Sample Input 1 5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1 Sample Output 1 1040
时间: 2024-03-31 09:36:49 浏览: 11
这是一个多重背包问题,每个物品可以购买多次,而且有数量限制。可以使用二进制拆分的方法将每个物品拆分成多个物品,每个新物品的数量为2的幂次方,即1、2、4、8、...等。这样就将多重背包问题转化为了01背包问题,可以使用一维的动态规划数组来解决。具体地,对于每个物品j,将其拆分成若干个新物品,其中第i个新物品的价值为i*w[j],重量为i*v[j],数量为1。然后就可以将其看作是01背包问题,使用一维的动态规划数组来解决。状态转移方程为:dp[i] = max(dp[i], dp[i-v[j]*2^k] + w[j]*2^k),其中v[j]为物品j的重量,w[j]为物品j的价值,k为二进制拆分后的指数。
下面是对应的C++代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXM = 6050;
const int MAXN = 505;
const int MAXS = 15;
int v[MAXN], w[MAXN], s[MAXN];
int dp[MAXM];
int main() {
int n, m;
cin >> n >> m;
int cnt = 1;
for (int i = 1; i <= n; i++) {
int vv, ww, ss;
cin >> vv >> ww >> ss;
for (int k = 1; k <= ss; k *= 2) {
v[cnt] = vv * k;
w[cnt] = ww * k;
s[cnt] = 1;
ss -= k;
cnt++;
}
if (ss > 0) {
v[cnt] = vv * ss;
w[cnt] = ww * ss;
s[cnt] = 1;
cnt++;
}
}
n = cnt - 1;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
for (int k = 0; k <= s[i] && k*v[i] <= j; k++) {
dp[j] = max(dp[j], dp[j-k*v[i]] + k*w[i]);
}
}
}
cout << dp[m] << endl;
return 0;
}
```