当前位置:网站首页>动态规划多重背包——庆功会(一维)
动态规划多重背包——庆功会(一维)
2022-07-21 08:02:00 【战士小小白】
庆功会(一维)
为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。
期望拨款金额能购买最大价值的奖品,可以补充他们的精力和体力。
输入格式
第一行二个数n,m,其中n代表希望购买的奖品的种数,m表示拨款金额。
接下来n行,每行3个数,v、w、s,分别表示第I种奖品的价格、价值(价格与价值是不同的概念)和能购买的最大数量(买0件到s件均可)。
输出格式
一行:一个数,表示此次购买能获得的最大的价值(注意!不是价格)。
数据范围
n≤500,m≤6000n≤500,m≤6000,
v≤100,w≤1000,s≤10v≤100,w≤1000,s≤10输入样例:
5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1
输出样例:
1040
#include <bits/stdc++.h>
using namespace std;
const int M = 6010;
int n, m;
int f[M];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)//第一维从小到大遍历物品种类(奖品的种数)
{
int v, w, s;//体积(价格)、价值(取max)、个数
scanf("%d%d%d", &v, &w, &s);
for(int j = m; j >= v; j --)//第二维从大到小遍历背包容量(拨款金额)
for(int k = 0; k <= s && k * v <= j; k++)//第三维从小到大遍历个数
f[j] = max(f[j], f[j - k * v] + k * w);
}
printf("%d", f[m]);
return 0;
}
边栏推荐
- Payment system - reconciliation system
- 2022年化工自动化控制仪表考试试题模拟考试平台操作
- (转)postMessage使用方法
- swift 【block】
- 阿里面试应该注意什么?通过5轮面试的阿里实习生亲述
- Learn the necessary tools of automation selenium think about automated testing in the pit again
- 05-1、默认成员函数:拷贝构造函数、赋值运算符重载
- 【集训DAY10】Linear【数学】【思维】
- 每个博主都需要问自己的7个基本问题
- Configuration and use of kaptcha verification code
猜你喜欢
奇葩!面试题目竟设置如厕习惯、吃饭时长、入睡时间
C language: leak detection and filling (I)
[Yugong series] go teaching course in July 2022 014 arithmetic operators of operators
windows10上安装mysql 5.7.37
Project practice four image mosaic
Using completable future to implement asynchronous callback
联想小新air13 pro重装win10时出现找不到存储设备驱动
tinymce 去掉编辑器换行默认增加的p标签
【集训DAY8】Series【矩阵乘法】
Learn the necessary tools of automation selenium think about automated testing in the pit again
随机推荐
叠氮化物标记pna肽核酸|亚甲基蓝标记pna肽核酸|酪氨酸修饰肽核酸PNA|Tyr-PNA齐岳bio
Kaptcha验证码的配置与使用
mysql8 貌似不支持myisam 分区表,PolarDB-X 支持myisam 的分区表吗?
【着色器实现Television信号三原色闪烁效果_Shader效果第五篇】
3. Project structure of source code analysis of Nacos configuration center
酪氨酸修饰肽核酸PNA|Tyr-PNA|Bz-Tyr-PNA|99Tcm—survivinmRNA反义肽核酸的使用方法
Stream流中的Map与flatMap的区别
05-1、默认成员函数:拷贝构造函数、赋值运算符重载
Easyexcel realizes file upload - batch insert file download
Ala-PNA丙氨酸改性PNA肽核酸|Ac-Ala-PNA的合成路线
FreeRTOS -- a method to detect the usage of task stack
Word2vec simple summary
44: Chapter 4: develop file service: 5: integrate fastdfs in [files] file service to realize the logic of [upload avatar]; (including: integrating fastdfs in the project; cross domain issues; creating
转载:CAN总线终端电阻
05-1. Default member function: copy constructor, assignment operator overload
The second financial article failed
C语言经典一百题(1-10题)(含答案)
Codeworks round 805 A-F problem solution
SPA单页面学习理解
SSM integrates other components