G6020 [GESP202512 六级] 道具商店 题解

知识点：0-1背包、值域动态规划、最小费用。

解题思路

价值总和较小而费用较大，用dp[v]表示取得总价值v的最低费用。每件商品倒序做0-1转移，最后找费用不超过k的最大价值。

为什么正确

买与不买穷尽单件选择，最低费用状态保留所有可能达到的价值，预算过滤后最大值即答案。

易错点

不能按巨大预算开数组；不可达状态用足够大的long long表示，容量倒序防止重复购买。

复杂度

设V为价值总和，时间O(nV)，空间O(V+n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin>>n>>k;
    vector<pair<int,long long>>a(n);
    int sum=0;
    for(auto &x:a) {
        cin>>x.first>>x.second;
        sum+=x.first;
    }
    vector<long long>dp(sum+1,1LL<<60);
    dp[0]=0;
    int now=0;
    for(auto [v,c]:a) {
        for(int j=now;j>=0;j--)dp[j+v]=min(dp[j+v],dp[j]+c);
        now+=v;
    }
    int ans=0;
    for(int j=0;j<=sum;j++)if(dp[j]<=k)ans=j;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。