列表

详情

NC213135. Knapsack

描述

Bobo has n items, where the i-th item has weight w_i and value v_i. He wants to pick some items whose sum of weights does not exceed m, and maximize the sum of values.

输入描述

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m. The i-th of the following n lines contains two integers w_i and v_i.

* 
* 
* 
* 
* The sum of n does not exceed .
* The sum of m does not exceed .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入: 

3 4
1 1
2 2
2 3
3 5
1 1
2 2
2 3
1 10
9 1000000000

输出: 

5
6
1000000000

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 216ms, 内存消耗: 1928K, 提交时间: 2020-11-02 19:25:05 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int nx=2e5+5;
struct node{
	int w,v;
}p[nx];
ll f[220];
bool cmp(node a,node b){
	return 1ll*a.v*b.w>1ll*b.v*a.w;
}
int main(){
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		for(int i=0;i<n;++i)scanf("%d%d",&p[i].w,&p[i].v);
		sort(p,p+n,cmp);
		int i=0;
		ll ans=0;
		for(;i<n&&m>200;++i)
			ans+=p[i].v,m-=p[i].w;
		memset(f,0,sizeof f);
		for(;i<n;++i)
			for(int j=m;j>=p[i].w;--j)
				f[j]=max(f[j],f[j-p[i].w]+p[i].v);
		printf("%lld\n",ans+f[m]);
	}
}

上一题

© 2025 nowcoder.com