张家齐
(张家齐)
1
庆功会
题目描述
八（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种物品。
数据范围
见题目
4 个赞
吴铭杨
(武媚娘)
4
应该是dp,好像是多组背包，可以用01背包，但可能会超时，希望能帮到你
3 个赞
崔静远
(崔静远)
5
现在我把代码发你：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+7;
int n,m;
int dp[N][N];
int c[N],w[N];
int vis[5007];
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>w[i]>>c[i]>>x;
w[i]*=x;
c[i]*=x;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][m]<<"\n";
for(int j=m;j>=0;j--){
for(int i=n;i>=1;i--){
if(dp[i][j]!=dp[i-1][j]){
vis[i]++;
j-=w[i];
}
}
}
for(int i=1;i<=n;i++){
if(vis[i]!=0) cout<<i<<" ";
}
return (0);
}
[poll type=regular results=always chartType=bar]
* 我是：全部抄袭！！！
* 我是：部分抄袭！！
* 我是：一点懂了！
* 我是：全部懂了（最希望是这种）
[/poll]
4 个赞
崩坏星穹铁道
(崩坏星穹铁道)
8
题目描述
时间：0. 1s 空间： 128 M
题目描述：
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
输入格式：
第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=1000。
输出格式：
第一行：一个数，表示此次购买能获得的最大的价值。
样例输入1：
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
样例输出1：
1040
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,num,cnt,w[5114],v[5114],s[5114],dp[6514];
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a>>b>>num;
for(int j=1; j<=num; j*=2) {
num-=j;
w[++cnt]=a*j;
v[cnt]=b*j;
}
if(num) {
w[++cnt]=a*num;
v[cnt]=b*num;
}
}
for(int i=1; i<=cnt; i++) {
for(int j=m; j>=w[i]; j--) {
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
return 0;
}
想想区别
3 个赞
