7. 庆功会
题目ID：1612必做题100分
最新提交：0 分
历史最高：0 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
八（1）班由于在期中考中获得了团体第一名，班主任吴老师决定开一场庆功会。于是购买东西的任务就交给了小李同学（钱由班会出）。由于小李同学四肢发达，头脑简单，于是这个任务便落到了你头上（当然不要你跑腿。跑腿是小李的事 ^_^）注：可以全买，但不能不买。即至少买1种
输入格式
第一行二个数n(n<=500)，m(m<=5000)，其中n代表希望购买的物品的种数，m表示班会拨给小李的钱数。接下来n行，每行3个数，v、w、s，分别表示第I种物品的价格、价值（价格 与 价值 是不同的概念）和购买数量（只能买0件或s件），其中v<=100,w<=1000,s<=10
输出格式
共两行：第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。第二行：小李此次购买（能获得的最大价值）所选择的物品种类的序号，序号按升序输出。
样例
Input 1
5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1
Output 1
1000 2 3 4 5
样例解释
输入第一行5 1000代表有5种物品，最多可以花1000元。下一行是每种物品的价值，价格和购买数量。最后的输出1000 2 3 4 5表示最大价值是1000，购买了第2、3、4、5种物品。
数据范围
见题目
#include<bits/stdc++.h>
using namespace std;
struct x {
int w, v, s,e;
bool q;
}a[500];
int main() {
int n, m;
int dp[5001] = { 0 };
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i].w >> a[i].v >> a[i].s;
a[i].e = i;
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= a[i].w; j--) {
int k = a[i].s;
if (j < k * a[i].w) break;
if (dp[j - k * a[i].w] + k * a[i].v > dp[j]) {
dp[j] = dp[j - k * a[i].w] + k * a[i].v;
a[i].q = 1;
}
else {
dp[j] = dp[j];
}
}
}
cout << dp[m]<<endl;
for (int i = 1; i <= n; i++) {
if (a[i].q == 1) {
cout << a[i].e<<" ";
}
}
return 0;
}
