动态规划解决商店购物问题
商店购物问题：
给定商店中每种商品的价格以及一组优惠价，其中优惠价指定将多种商品捆绑销售时的折扣价格。顾客购买了一组商品，求最少需要支付的金额。
动态规划算法：
- 定义状态：
dp[i][j]表示购买前i种商品，数量为j时的最小总价。 - 状态转移方程：
dp[i][j] = min(dp[i-1][j], dp[i][j-1] + p[i])
其中，p[i] 为第 i 种商品的原价。
3. 边界条件：
dp[0][0] = 0
dp[i][0] = dp[0][j] = ∞
- 计算顺序：从
dp[1][1]开始，按i和j的顺序依次计算所有状态。
具体示例：
已知花朵价格为 2 ICU，花瓶价格为 5 ICU，优惠价为：3 朵花 5 ICU，2 个花瓶 + 1 朵花 10 ICU。顾客购买 3 朵花和 2 个花瓶，使用动态规划算法可以计算出最少需要支付的金额为 14 ICU。
文件大小：3.98MB
评论区