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

一、题目解读

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

二、解题思路

采用动态规划(DP)的方法解决这个问题。核心思想是构建一个二维数组dp，其中dp[i][j]表示前i种饮料在容量j时的最小花费。通过遍历所有饮料和所有可能的容量，逐步填充这个二维数组，最终得到最优解。

三、解题步骤

1. 输入饮料种类数n和背包容量l

2. 创建数组v和w分别存储每种饮料的价格和体积

3. 初始化二维dp数组，边界条件设置为0

4. 双重循环填充dp数组：

• 外层循环遍历所有饮料

• 内层循环遍历所有可能的容量

• 根据当前饮料是否放入背包更新dp值

5. 输出最终结果，若无解则输出"no solution"

四、代码实现(附注释)

#include<iostream>
using namespace std;

int main()
{
	int n, l;  // n为饮料种类数，l为背包容量
	cin >> n >> l;
	int* v = new int[n];  // 存储每种饮料的价格
	int* w = new int[n];  // 存储每种饮料的体积
	for (int i = 0; i < n; i++)
	{
		cin >> v[i] >> w[i];  // 输入每种饮料的价格和体积
	}
	
	// 初始化动态规划数组dp
	int** dp = new int* [n + 1];
	for (int i = 0; i <= n; i++)
	{
		dp[i] = new int[l + 1];
		for (int j = 0; j <= l; j++)
		{
			if (!i or !j)dp[i][j] = 0;  // 边界条件初始化
		}
	}
	
	// 填充dp数组
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= l; j++)
		{
			if (w[i-1] > j)dp[i][j] = v[i-1];  // 当前饮料体积超过剩余容量
			else dp[i][j] = min(dp[i - 1][j], v[i-1]+dp[i - 1][j - w[i-1]]);  // 取最小值
		}
	}
	
	// 输出结果
	if (dp[n][l] == 0)cout << "no solution";
	else cout << dp[n][l];

	return 0;
}

五、总结

这道题目很好地考察了动态规划在实际问题中的应用。通过构建二维dp数组，我们可以系统地解决这类背包问题变种。关键在于理解状态转移方程和边界条件的处理。掌握这种解题思路对参加编程竞赛和算法考试都有很大帮助。