首页 > 编程语言 >南沙C++信奥赛陈老师解一本通题 1269:【例9.13】庆功会

南沙C++信奥赛陈老师解一本通题 1269:【例9.13】庆功会

时间:2024-09-30 10:38:16浏览次数:7  
标签:奖品 1269 背包 20 6001 int 信奥赛 庆功会 dp

 【题目描述】

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

【输入】

第一行二个数n(n≤500),m(m≤6000),其中n代表希望购买的奖品的种数,m表示拨款金额。

接下来nn行,每行33个数,v、w、s,分别表示第I种奖品的价格、价值(价格与价值是不同的概念)和能购买的最大数量(买00件到ss件均可),其中v≤100,w≤1000,s≤10。

【输出】

一行:一个数,表示此次购买能获得的最大的价值(注意!不是价格)。

【输入样例】

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

【输出样例】

1040

 

#include <iostream>
using namespace std;
int dp[6001][6001];  //i为行件物品放到容易为j为列的背包产生的最大价值 
int w[6001],v[6001]; //w重量,v代表价格 
int main()
{
	int n,m,wi,vi,si,cnt=0;  //m表示背包容量 n表示物品个数  cnt表示转成0-1背包后物品的个数 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>wi>>vi>>si;
		//将第i物品有si件存入数组 从而将多重背包转成0-1背包 
		for(int j=1;j<=si;j++)
		{
			cnt++;
			w[cnt]=wi;
			v[cnt]=vi;
		}
	}
	for(int i=1;i<=cnt;i++) 	//要变成k件物品,而不是m件物品 
	{
		for(int j=1;j<=m;j++)
		{
			if(w[i]>j)
				dp[i][j]=dp[i-1][j];
			else
			{
				int put=v[i]+dp[i-1][j-w[i]];
				int noput=dp[i-1][j];
				dp[i][j]=max(put,noput);
			}
		}
	}
	cout<<dp[cnt][m];	
	return 0;
}

 

标签:奖品,1269,背包,20,6001,int,信奥赛,庆功会,dp
From: https://www.cnblogs.com/nanshaquxinaosai/p/18441345

相关文章

  • 南沙C++信奥赛陈老师解一本通题 1922:【03NOIP普及组】乒乓球
    ​ 【题目描述】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓球研究工作,意图弄明白11分制和21分制对选手的不......
  • 南沙C++信奥赛陈老师解一本通题 1942:【08NOIP普及组】ISBN号码
    ​ 【题目描述】每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一位是识别码,例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语音,例如......
  • 南沙C++信奥赛陈老师解一本通题 1973:【16NOIP普及组】买铅笔
    ​ 【题目描述】P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有3种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起见,P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装拆开,因此P老师可能需要购买超过n支铅笔才够给小......
  • 南沙C++信奥赛老师解一本通题1217:棋盘问题
    ​ 【题目描述】在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放 kk 个棋子的所有可行的摆放方案 CC。【输入】输入含有多组测试数据。每组数据......
  • 广州C++信奥赛老师解一本通题 1389:亲戚
    ​ 【题目描述】若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的某个人所在家族的人数。规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。【输入】第一行:三个整数n,(n......
  • 南沙信奥赛C++陈老师解一本通题: 1326:【例7.5】 取余运算(mod)
    ​【题目描述】【输入】输入b,p,k的值。【输出】【输入样例】2109【输出样例】2^10mod9=7 #include<iostream>#include<stdlib.h>usingnamespacestd;longlongb,p,k,ans=1;intmain(){ cin>>b>>p>>k; for(inti=1;i<=p;i++) { ans*=b;......
  • 南沙信奥赛C++陈老师解一本通题: 1171:大整数的因子
    ​ 【题目描述】已知正整数k满足2≤k≤9,现给出长度最大为30位的十进制非负整数c,求所有能整除c的k。【输入】一个非负整数c,c的位数≤30。【输出】若存在满足 c%k==0的k,从小到大输出所有这样的k,相邻两个数之间用单个空格隔开;若没有这样的k,则输出"none"。【输入样......
  • 信奥赛C++老师解一本通题:1182:合影效果
    ​【题目描述】小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他们合影的效果是什么样的(所有人的身高都不同)?【输入】第一行是人数nn(2≤n≤......
  • 信奥赛C++老师解一本通题:1938:【07NOIP普及组】奖学金
    ​【题目描述】某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排......
  • 信奥赛C++老师解一本通题: 1180:分数线划定
    ​ 【题目描述】世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定,即如果计划录取m名志愿者,则面试分数线为排名第m×150%(向下取整)名的选手......