GESP 2023年 六级 小杨买饮料 洛谷P3873题 解题思路和步骤 C++实现带注释 洛谷 leetcode

题目分析

该题属于动态规划中的01背包问题变种，要求选择若干种饮料（每种至多选一次），在总容量不低于L的前提下使花费最小。与标准01背包的区别在于：

1. 1.容量要求是"不低于"而非"不超过"

2. 2.需要处理无解情况

3. 
   

解题思路

1. ‌1.状态定义‌：设DP[j]表示达到容量j时的最小花费

2. ‌2.初始化‌：dp[0]=0（0容量花费为0），其他初始化为INF（表示不可达）‌

3. 3.状态转移‌：对于每种饮料，逆序更新dp数组：dp[j] = min(dp[j], dp[max(j-w,0)] + c)

4. ‌4.结果处理‌：在dp[L...maxL]范围内找最小值

5. 
   

实现步骤

1. 1.输入饮料种类数N和需求容量L

2. 2.初始化dp数组

3. 3.处理每种饮料，更新dp值

4. 4.检查是否有解并输出结果

5. 
   

代码实现

#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1e9; // 定义无穷大值

int main() {
    int N, L;
    cin >> N >> L;
    
    int cost[2001]; // dp数组
    cost[0] = 0;    // 初始状态
    for(int i = 1; i <= 2000; i++) 
        cost[i] = INF; // 初始化
    
    // 处理每种饮料
    for(int i = 0; i < N; i++) {
        int c, w; // 价格和容量
        cin >> c >> w;
        
        // 逆序更新dp数组
        for(int j = 2000; j >= 0; j--) {
            int new_j = min(j + w, 2000); // 防止数组越界
            cost[new_j] = min(cost[new_j], cost[j] + c);
        }
    }
    
    // 在[L,2000]范围内找最小值
    int ans = INF;
    for(int j = L; j <= 2000; j++) 
        ans = min(ans, cost[j]);
    
    if(ans == INF) cout << "no solution";
    else cout << ans;
    
    return 0;
}

该解法时间复杂度O(N*maxL)，其中maxL为最大可能容量2000。关键点在于逆向更新dp数组和结果范围的处理。