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

· · 题解

前言

一道非常简单的 01 背包变形。

题目传送门

简述

小杨来到一家商店买饮料，商店有 N 种饮料，编号 0 到 N-1。第 i 种饮料的价格是 c_i 元，容量是 l_i 毫升。小杨的要求是：

  1. 每种饮料最多买 1 瓶。

  2. 购买的饮料总容量至少为 L 毫升。

  3. 在满足前两个条件的情况下花费最少。

如果无法满足条件，输出 no solution。

本题思路

本题是一个相对简单的背包，目标是选择若干种不同的饮料，使得它总容量至少为 L 毫升，并且总花费最小。

由于每种饮料只有选或不选两种情况，可以用 01背包求解。

首先，定义 dp _ {i,j} 表示 从前 i 种饮料中选择，使得总容量至少为 j 毫升时的最小花费。

初始化时，要使 dp[0][0]=0（什么也不选也是 1 种方案），dp 数组其余设为无穷大（因为要找最小值）。

接下来，遍历每种饮料，并考虑选或不选它：

1.不选第 i 种饮料：dp[i][j] = dp[i-1][j]，直接从之前的状态继承。

2.选第 i 种饮料：

如果该饮料的容量 l[i] 已经满足 j，则只需要花费 c[i] 元。否则，还需要从前 i-1 种饮料中补充 j-l[i] 的容量，即 dp[i][j]=dp[i-1][j-l[i]]+c[i]。

当然，为了避免 j-l[i] 为负数，我们取 prev=max(0,j-l[i])，确保剩余需求不会小于 0。

最终，dp[N][L] 就是答案：如果它仍然是无穷大，说明无法满足需求，输出 no solution；否则，输出 dp[N][L]。

代码

#include<bits/stdc++.h>
using namespace std;
int N,L,c[505],l[505],dp[505][2005]//前 i 种饮料中选，使得总容量至少为 j 毫升时的最小花费。
int main(){
    cin>>N>>L;
    for(int i=1;i<=N;i++){
        cin>>c[i]>>l[i];
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;//什么也不选也是 1 种方案。 
    for(int i=1;i<=N;i++){
        for(int j=0;j<=L;j++){
            //不选。 
             dp[i][j]=dp[i-1][j];
            //选第 i 种饮料。
            int prev=max(0,j-l[i]);//目标不是恰好装满，而是至少达到 L 容量。
            if(dp[i-1][prev]+c[i]<dp[i][j]){
                dp[i][j]=dp[i-1][prev]+c[i];
            }
        } 
    }
    if(dp[N][L]!=0x3f3f3f3f){//被更新。 
        cout<<dp[N][L];
    }else{
        cout<<"no solution";//未被更新。
    }
    return 0;
}