GESP六级真题解析：动态规划解决小杨买饮料问题(洛谷3873)

19339201706

一、题目解读

小杨买饮料是GESP 2023年六级认证考试中的一道经典动态规划题目，考察学生对背包问题的理解和应用能力。题目描述小杨需要购买n种饮料，每种饮料有特定的体积w和价格v，他要在不超过容量l的情况下，选择最便宜的购买方案。这道题实质上是背包问题的变种，需要运用动态规划思想求解。

二、解题步骤

• 输入饮料种类数n和背包容量l
• 创建数组v和w分别存储每种饮料的价格和体积
• 初始化二维dp数组，边界条件设置为0
• 双重循环填充dp数组：
  
  
  • 外层循环遍历所有饮料
  • 内层循环遍历所有可能的容量
  • 根据当前饮料是否放入背包更新dp值
    
    
• 输出最终结果，若无解则输出"no solution"
  
  

三、代码实现

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.         int n, l;
   
7.         cin >> n >> l;
   
8.         int* v = new int[n];
   
9.         int* w = new int[n];
   
10.         for (int i = 0; i < n; i++)
    
11.         {
    
12.                 cin >> v[i] >> w[i];
    
13.         }
    
14.         int** dp = new int* [n + 1];
    
15.         for (int i = 0; i <= n; i++)
    
16.         {
    
17.                 dp[i] = new int[l + 1];
    
18.                 for (int j = 0; j <= l; j++)
    
19.                 {
    
20.                         if (!i or !j)dp[i][j] = 0;
    
21.                 }
    
22.         }
    
23.         for (int i = 1; i <= n; i++)
    
24.         {
    
25.                 for (int j = 1; j <= l; j++)
    
26.                 {
    
27.                         if (w[i-1] > j)dp[i][j] = v[i-1];
    
28.                         else dp[i][j] = min(dp[i - 1][j], v[i-1]+dp[i - 1][j - w[i-1]]);
    
29.                 }
    
30.         }
    
31.         if (dp[n][l] == 0)cout << "no solution";
    
32.         else cout << dp[n][l];
    
33. 
    
34.         return 0;
    
35. }

复制代码

转自：GESP六级真题解析：动态规划解决小杨买饮料问题(洛谷3873)