首页 分享 经典算法动态规划之商品最优购买问题

经典算法动态规划之商品最优购买问题

来源:花匠小妙招 时间:2024-11-14 14:24

问题描述

最小费用购物:
商店中每种商品都有标价。例如,一朵花的价格是2元,一个花瓶的价格是5元。为了吸引客户,商店提供了一组优惠价格商品。优惠价格是把一种或者多种商品分成一组,并且降价销售。例如:三朵花的价格不是6元而是5元。2个花瓶加一朵花的优惠价格是10元。是设计一种算法,计算出某一顾客所购商品应付的最小费用。

题目分析

首先我们考虑这样的问题,当我们通过一种优惠方案以后,那么会产生一个新的子问题,而且产生同样的状态可能不止一条路经,但是这个状态的最小值只有一个,那么这个题目是满足无后效性,又有大量重叠子问题,还符合最优化原理,那么我们选择动态规划来做这道题目是十分合适的。

算法思想实现

通过遍历整张dp表, 我们可以从(0, 0, 0, 0, 0)到(a,b,c,d,e)一直遍历,我们分别以此此判断整个表的每个状态的最小值,当满足某种优惠条件时候,我们把当前状态减去一个优惠方案,会得到一个之前已经算过的重复状态,我们可以通过查表法轻松的得到这个答案,如果满足多个优惠方案,那么我们需要把这几个方案返回的最小值计算出来,填入表中。如果不满足,直接返回单价×数量。这样经过一次遍历以后,我们就可以完整的得到这个dp表,并且实现了备忘录功能,消除了大量重叠子问题。

代码设计思路

我们可以通过一个多维数组来实现这个dp表,每次遍历表中的每个数据,分支进行判断所有优惠方案,并且返回每个分支的值,再这些值当中取得一个最小值放入表中。
数据设计以及测试用例:
2 //代表用户购买两种商品
7 8 2 //七号商品,买8个,单价两元
8 11 5 //八号商品,买11个,单价五元

2 //两种优惠方案
1 7 3 5 //优惠方案涉及1种商品,编号为7,需要3个,优惠价格为5元
2 7 1 8 2 10 // 优惠方案涉及2种商品,编号为7,需要1个。编号为8,需要两个。优惠价格为10元

最后得到整个最小优惠价格:价格的期望值为60。

算法图解

在这里插入图片描述

代码展示

def MinCost(): # 创建一个dp五维数组表,用来做成备忘录 dp[6][6][6][6][6] dp = [] for a in range(10): dp.append([]) for b in range(10): dp[a].append([]) for c in range(10): dp[a][b].append([]) for d in range(10): dp[a][b][c].append([]) for e in range(10): dp[a][b][c][d].append(0) # 定义一个商品列表 goods[5][3] goods = [] for a in range(5): goods.append([]) for b in range(3)

12345678910111213141516171819

相关知识

算法(七)100个经典的动态规划方程
基于正余双弦自适应灰狼优化算法的医药物流配送路径规划
求解物流配送问题的混合粒子群算法
整数规划的花授粉算法
物流配送路径规划模型及其改进TLBO算法研究
基于动态交通网络的城市物流配送路径优化研究
【优化覆盖】基于matlab入侵杂草和花授粉混合算法无线传感器覆盖优化问题【含Matlab源码 1328期】
K近邻算法和鸢尾花问题
花店橱窗布置(洛谷P1854)(动态规划)
适应性花朵授粉算法研究

网址: 经典算法动态规划之商品最优购买问题 https://www.huajiangbk.com/newsview547473.html

所属分类:花卉
上一篇: 2022武汉花博汇春季门票优惠政
下一篇: 【练习】

推荐分享