G6001 [GESP202309 六级] 小杨买饮料 题解

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

解题思路

令dp[v]为已获得容量v的最小费用，把所有达到L的容量合并到状态L。逐种饮料倒序枚举容量，转移到min(L,v+l_i)。

为什么正确

倒序保证每种饮料至多一次，取最小费用穷尽“买或不买”两类方案，合并超额容量不影响达到需求后的目标。

易错点

这是0-1背包，容量必须倒序；无可达状态时输出no solution，而非0。

复杂度

时间O(nL)，空间O(L)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,L;
    cin>>n>>L;
    vector<long long>dp(L+1,1LL<<60);
    dp[0]=0;
    while(n--) {
        int c,v;
        cin>>c>>v;
        for(int j=L;j>=0;j--)dp[min(L,j+v)]=min(dp[min(L,j+v)],dp[j]+c);
    }
    if(dp[L]==(1LL<<60))cout<<"no solution";
    else cout<<dp[L];
}

说明

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