UPC19274: 魔幻背包
admin
2024-05-05 12:03:29
0次

题目描述

Bob 是个聪明的小孩，他在小学的时候就已经掌握了 01 背包的使用方法。所谓 01 背包问题，就是从 n 个物品中（每个物品有 w[i]的重量和 v[i]的价值）选出若干个，每个物品可以选或者不选，使得在总重量不超过 m 的情况下，总价值最大。

有一天，Bob 买到了一个背包，这个背包能够承受重量也是 m。不一样的是，这个背包有一个特别的性质：如果背包还没满的话，放入下一件物品之后，背包内的重量可以超过 m。例如有 3 件物品，物品 1 的重量和价值分别为 3,3，物品 2 的为 2,1，物品 3 的为 3,3。假如背包的承受重量 m 为 6：

第一种情况下：先放入物品 1，3；则此时背包已满，不能放入物品 2，故最后的总价值为 6。

第二种情况下：先放入物品 1，2；此时背包中的重量为 5，还没有满，故可以继续放入物品 3。此时虽然背包的重量为 8，但是符合我们的条件，因此总价值为 7。

输入

输入一共有 3 行，第一行依次为 n（物品数量）,m（背包重量）。其中 n≤2000，m≤2000。

第二行包含 n 个整数 w[i]（1≤Wi≤2000）。

第三行包含 n 个整数 v[i]（1≤Ci≤10^6）。

输出

输出共一行，为使用这个神奇背包能背的最大价值总和。

样例输入

【样例1】

3 6

3 3 2

3 3 1

【样例2】

3 5

3 3 2

3 3 10

样例输出

【样例1】

7

【样例2】

13

提示

对 30%的数据，n<20。

对 60%的数据，n<100。

对 100%的数据，n≤2000。

取一个v+maxv体积的背包即可，简单题

#include
using namespace std;
#define int long long
const int N=4010;
int dp[N];
int f[N];
int n,m;
struct node
{int w,v;
} Node[N];
bool cmp(node a,node b)
{return a.w>n>>m;int maxf=0;for(int i=1; i<=n; i++){cin>>Node[i].w;maxf=max(maxf,Node[i].w);}for(int i=1; i<=n; i++){cin>>Node[i].v;}sort(Node+1,Node+1+n,cmp);//    cout<=Node[i].w; j--){if(dp[j]=0; j--){mmax=max(mmax,dp[j]);}cout<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：不断抽贷阿里旗下又一企业败走江湖，网商银行资产缩水高达500亿 阿里网商银行现状 网商贷反复抽贷又恢复是什么问题

下一篇：重大信号！暂停新增商品住宅用地出让！南昌…… 南昌市可拍的住宅用地 南昌2024年商品住宅供地计划

相关内容

热门资讯

现货黄金突破前高，逼近3800... 9月29日消息，现货黄金突破前高，将历史新高刷新至3793美元/盎司，日内涨约0.8%。（广角观察）
9月28日新闻联播速览22条 9月28日消息，今天《新闻联播》主要内容有：1.习近平对党校（行政学院）工作作出重要指示强调 坚持党...
消息称欧佩克+或在10月会议上... 9月28日消息，有媒体援引消息人士称，欧佩克+可能在下周日的会议上再次批准石油产量增加至少13.7万...
上海：要精心打造金秋消费新热潮... 9月28日消息，上海市委副书记、市长龚正今天（9月28日）主持召开市政府常务会议。会议指出，国庆、中...
联合国确认安理会涉伊朗制裁决议... 9月28日消息，联合国秘书长发言人办公室确认，联合国秘书长根据安理会第2231号决议相关条款，安理会...
国家发展改革委主任郑栅洁主持召... 9月28日消息，国家发展改革委主任郑栅洁9月28日主持召开民营企业座谈会，就“十五五”时期扩大有效投...
圣泉集团：拟发行可转债募资不超... 9月28日消息，圣泉集团(605589.SH)公告称，公司拟向不特定对象发行可转换公司债券，募资总额...
光明乳业：子公司新莱特拟出售新... 9月28日消息，光明乳业(600597.SH)公告称，下属子公司新莱特拟以1.7亿美元向新西兰雅培出...
中泰股份：董事、高管拟合计减持... 9月28日消息，中泰股份公告，公司董事兼高级管理人员章有虎、唐伟、周娟萍，董事俞富灿、刘晓庆，拟通过...
龙蟠时代已于9月25日停产，预... 9月28日消息，从锂电业内人士处获悉，因为宁德时代宜春锂矿停止供应原材料，宁德时代和龙蟠科技合资公司...