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

· · 题解

简化题意：

有 n 个物品和初始金额 W，每个物品有价格 w_i 和 美丽度 v_i，我们可以免费获得最多 k 件物品，求可以花费 W 可获得的最大美丽度为多少。

思路：

对于如何利用这 k 次零元购，可以想到两种思路：

  1. 选取 k 个美丽度最大的。
  2. 选取 k 个价格最大的。

但显然对于思路 1，若我们只考虑美丽度而没有考虑价格，可能会导致我们只能得到 k 个美丽度最大的而剩下的物品每个我们都买不起。因此采用第 2 种贪心方案，我们把价格大的物品尽可能多免费得到，剩下的价格较小的尽可能多买。 对所有数据按照价格从小到大排序后。每次求 1 \sim i 求解 01 背包，对于剩下的 n - i 选取 k 个价值最大的。

代码

#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;
}