题解：P13957 [ICPC 2023 Nanjing R] 背包

简化题意：

有

n

个物品和初始金额

W

，每个物品有价格

w_i

和美丽度

v_i

，我们可以免费获得最多

k

件物品，求可以花费

W

可获得的最大美丽度为多少。

思路：

对于如何利用这

k

次零元购，可以想到两种思路：

选取 $k$ 个美丽度最大的。
选取 $k$ 个价格最大的。

但显然对于思路 1，若我们只考虑美丽度而没有考虑价格，可能会导致我们只能得到

k

个美丽度最大的而剩下的物品每个我们都买不起。因此采用第 2 种贪心方案，我们把价格大的物品尽可能多免费得到，剩下的价格较小的尽可能多买。对所有数据按照价格从小到大排序后。每次求

1 \sim i

求解 01 背包，对于剩下的

n - i

选取

k

个价值最大的。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 5e3 + 10;
const int M = 1e4 + 10;
int n,W,k;
int f[M];
struct Node{
	int w,v;
}a[N];
int ans;
bool cmp(Node x,Node y){return x.w < y.w;}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> W >> k;
	for(int i = 1;i <= n;i ++){
		int w,v;
		cin >> w >> v;
		a[i] = {w,v};
	}
	sort(a + 1,a + 1 + n,cmp);
	for(int i = 1;i <= n;i ++){
		for(int j = W;j >= a[i].w;j --){
			f[j] = max(f[j],f[j - a[i].w] + a[i].v);
		}
		priority_queue<int>q;//优先队列自动排序，也可以使用数组sort排序 
		for(int p = i + 1;p <= n;p ++)q.push(a[p].v);
		int now = f[W];//花钱前i个物品的最大美丽度 
		int m = min((int)q.size(),k);
		while(m --){
			now += q.top();
			q.pop();
		}
		ans = max(now,ans);
	}
	cout << ans;
	return 0;
}

题解：P13957 [ICPC 2023 Nanjing R] 背包

文章操作

简化题意：

思路：

代码

相关推荐

评论

题解：P13957 [ICPC 2023 Nanjing R] 背包