2018年全国多校算法寒假训练营练习比赛(第二场) B TaoTao要吃鸡 01背包变形题
2024-09-01 07:39:35
链接:https://www.nowcoder.com/acm/contest/74/B
来源:牛客网
Taotao的电脑带不动绝地求生,所以taotao只能去玩pc版的荒野行动了,
和绝地求生一样,游戏人物本身可以携带一定重量m的物品,装备背包
之后可以多携带h(h为0代表没有装备背包)重量的东西。玩了几天
taotao发现了一个BUG,当装备背包之后,如果可携带重量没有满,就
可以拿一个任意重的东西。(解释看样例)有一天taotao空降到了一个
奇怪的岛上,岛上有n件装备,每个装备都有重量Wi和威力值Vi,但taotao
不认识这些装备,所以他来求助你,挑选威力最大的装备,帮助他吃鸡。
输入描述:
本题有多组输入(小于10),当n=0时结束输入。
第一行输入n,m,h。n,m,h为整数,并且0<=n,m,h<=100,
接下来n行,每行输入第i个物品的物品的重量Wi和威力值Vi。0<=Wi,Vi<=100.
输出描述:
输出最大威力值,每组输出一行。
输入例子:
3 3 3
2 3
3 2
2 3
0
输出例子:
8
-->
示例1
输入
3 3 3
2 3
3 2
2 3
0
输出
8
说明
可携带的总重量为6,当拿了前两件装备,此时容量为5/6,还可以再拿第三件物品。 当没有加背包的时候,是一个单纯的01背包问题。只要考虑在m容量下放进价值最大的物品。
当加了背包后,是01背包问题的变形题,因为题目的要求是最后一个可以任意重量,所以我们在判断时,每次加上循环进行到的物品的重量,判断是否大于容量,大于就更新背包可放最大价值。若没有更新此重量下的背包最大价值。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <stack>
#include <set>
#define debug(a) cout << #a << " = " << a <<endl
using namespace std;
typedef long long ll;
const int maxn = + ;
int w[maxn],v[maxn],dp[maxn*];
struct node {
int w,v;
};
node a[maxn];
bool cmp( node p, node q ) {
return p.w < q.w;
}
int main() {
int n,m,h;
while( cin >> n ) {
if( !n ) {
break;
}
cin >> m >> h;
for(int i = ; i < n; i ++ ) {
cin >> a[i].w >> a[i].v;
}
sort(a,a+n,cmp);
memset(dp,,sizeof(dp));
if( h == ) { //没有加背包的时候
for( int i = ; i < n; i ++ ) {
for( int j = m; j >= a[i].w; j -- ) {
dp[j] = max( dp[j], dp[j-a[i].w]+a[i].v );
}
}
cout << dp[m] << endl;
} else { //加了背包的时候
m += h;
for( int i = ; i < n; i ++ ) {
for( int j = m-; j >= ; j -- ) {
if( j + a[i].w < m ) { //是否大于容量,大于就更新最大价值,因为最后一个重量可以任意
dp[j+a[i].w] = max( dp[j+a[i].w], dp[j]+a[i].v );
} else {
dp[m] = max( dp[m], dp[j]+a[i].v );
}
}
}
cout << dp[m] << endl;
}
}
return ;
}
最新文章
- C#语法糖
- Run python as a daemon process
- xcode的菜单栏功能解析
- JPA EntityManager详解(一)
- for循环进阶
- Cocos2d-x——CocosBuilder官方帮助文档翻译1 使用自定义类
- jq交叉轮播图变种【闪一下黑】
- php无限极分类的实现
- springboot配置视图控制器
- 将mnist数据集保存成numpy格式
- Unity3D用户手册
- BZOJ.3064.CPU监控(线段树 历史最值)
- 基于php,点亮代码生成技能树
- EXCEL小技巧:如何统计非空单元格
- 搭建Linux-java web运行环境之二:安装mysql
- PHP include 和 require 语句 (调用其他php文件进来的方法)
- mysql-5.7 密码过期详解
- 160225、解决纯js文件国际化的问题
- [POI2015]LOG
- java console 到文件