GESP六级真题解析：动态规划解决小杨买饮料问题(洛谷3873)
一、题目解读小杨买饮料是GESP 2023年六级认证考试中的一道经典动态规划题目，考察学生对背包问题的理解和应用能力。题目描述小杨需要购买n种饮料，每种饮料有特定的体积w和价格v，他要在不超过容量l的情况下，选择最便宜的购买方案。这道题实质上是背包问题的变种，需要运用动态规划思想求解。二、解题步骤[*]输入饮料种类数n和背包容量l
[*]创建数组v和w分别存储每种饮料的价格和体积
[*]初始化二维dp数组，边界条件设置为0
[*]双重循环填充dp数组：
[*]外层循环遍历所有饮料
[*]内层循环遍历所有可能的容量
[*]根据当前饮料是否放入背包更新dp值
[*]输出最终结果，若无解则输出"no solution"
三、代码实现
#include<iostream>
using namespace std;
int main()
{
int n, l;
cin >> n >> l;
int* v = new int;
int* w = new int;
for (int i = 0; i < n; i++)
{
cin >> v >> w;
}
int** dp = new int* ;
for (int i = 0; i <= n; i++)
{
dp = new int;
for (int j = 0; j <= l; j++)
{
if (!i or !j)dp = 0;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= l; j++)
{
if (w > j)dp = v;
else dp = min(dp, v+dp]);
}
}
if (dp == 0)cout << "no solution";
else cout << dp;
return 0;
}转自：GESP六级真题解析：动态规划解决小杨买饮料问题(洛谷3873)
页:
[1]