首页 > 其他分享 >DP--背包问题

DP--背包问题

时间:2022-10-26 20:36:31浏览次数:53  
标签:小明 背包 题目 -- int DP return dp Vec


小明同学在参加一场考试,考试时间2个小时。试卷上一共有n道题目,小明要在规定时间内,完成一定数量的题目。  考试中不限制试题作答顺序,对于 i 第道题目,小明有三种不同的策略可以选择:  (1)直接跳过这道题目,不花费时间,本题得0分。

(2)只做一部分题目,花费pi分钟的时间,本题可以得到ai分。  (3)做完整个题目,花费qi分钟的时间,本题可以得到bi分。 

小明想知道,他最多能得到多少分。

 

输入描述:


第一行输入一个n数表示题目的数量。 接下来n行,每行四个数p_i,a_i,q_i,b_i。(1≤n≤100,1≤p_i≤q_i≤120,0≤a_i≤b_i≤1000 )。


 

输出描述:


输出一个数,小明的最高得分。


 

输入例子1:


4 20 20 100 60 50 30 80 55 100 60 110 88 5 3 10 6


 

输出例子1:


94


#include<iostream>
#include<vector>
using namespace std;

int MAX(const int a,const int b,const int c){
if(a > b && a > c){
return a;
}
else if(b > a && b > c){
return b;
}
else{
return c;
}
}

int main(){
int n;
scanf("%d",&n);
vector<vector<int>> Vec(n,vector<int>(4));
vector<vector<int>> dp(n + 1,vector<int>(121,0));
for(int i = 0;i < n;i ++){
for(int j = 0;j < 4;j ++){
scanf("%d",&Vec[i][j]);
}
}
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= 120;j ++){
if(Vec[i - 1][0] > j){
dp[i][j] = dp[i - 1][j];
}
else if(Vec[i - 1][0] <= j && j < Vec[i - 1][2]){
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - Vec[i - 1][0]] + Vec[i - 1][1]);
}
else{
dp[i][j] = MAX(dp[i - 1][j],dp[i - 1][j - Vec[i - 1][0]] + Vec[i - 1][1],dp[i - 1][j - Vec[i - 1][2]] + Vec[i - 1][3]);
}
}
}
int Result = dp[n][120];
printf("%d\n",Result);
return 0;
}

 

标签:小明,背包,题目,--,int,DP,return,dp,Vec
From: https://blog.51cto.com/u_13121994/5798380

相关文章

  • 数组最大间隔
    题目描述小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。......
  • 括号匹配
     合法的括号匹配序列被定义为:1.空串""是合法的括号序列2.如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列3.如果"X"是一个合法的序列,那么"[X]"也是一个......
  • m个求放入到n个瓶子的组合数
    题目描述要把m升的水倒入n个相同的容器中(假设容器足够大),允许有的容量是空的,问共有多少种不同的倒法?(用k表示)5,1,1和1,5,1和1,1,5是同一种倒法。 输入描述:第一行是测试数据的数目......
  • weka遇到java.util.zip.ZipException: invalid LOC header (bad signature)
    这是因为有jar包没有下载完全引起的,需要将相应包重新下载。到maven的reposity目录下搜aether*****in-progress(可以搜aether或者in-progress都行)文件,如果存在,把这个文件对......
  • python爬虫练习3
    说明python3.6.132位获取豆瓣电影推荐页电影详情,参考网址​​​https://movie.douban.com/explore#!type=movie&tag=%E7%83%AD%E9%97%A8&sort=recommend&page_limit=20&......
  • arcgis/arcmap面共用边
    需求说明有些地质现象、遥感解译等面需要共用边,一般情况下,可以先画出整体范围,然后使用裁剪面工具,但是有时是先画出了局部,欲在此基础上补充紧邻的面。解决方案使用创建要素......
  • python入门基础之第三方模块
    python入门基础之第三方模块第三方模块的下载与使用所谓第三方模块,就是别人写的模块,一般功能都比较强大。我们如果想使用第三方模块,第一次必须先下载后面才可以反复使用(......
  • Envi ROI Tool的Record Count为0
    问题描述Envi5.1和5.2的新版的ROITool画完感兴趣后,导出.roi文件,如下图:再次打开时,Recordcount为0(,通过enviclassic可以知道,绘制的面变成了像素点),使得不能对单个面进行定......
  • 哪些因素会影响sqlserver shrink的速度
    以下因素会严重影响sqlserver文件收缩的时间。1.LOB数据所谓LOB数据,指的是任何大值数据类型(如text、image、varchar(max)、XML)。这里的问题在于存储LOB值的方式,他们通......
  • ASCII码经典对照图
    ASCII码经典对照图......