第四次实验_算法_动态规划——硬币支付问题_V2_

简介：
本篇文章探讨了使用动态规划解决硬币支付问题的算法。通过详细分析与多次迭代优化，提出了一种高效的解决方案，以最小化硬币数量达到最佳支付方式。这是对先前研究的一次重要改进和补充。 设有n种不同面值的硬币，第i种硬币的价值是vk（其中v1=1），重量为wi，且i取值从2到n。现在需要购买总价值为y的商品，并用这些硬币支付。如果每一种钱币使用的数量不限制，请设计一个算法来选择付款方式，使得付出的货币总重量最轻。请给出该问题求解算法的伪码描述并分析其时间复杂度。 假设输入实例如下： v1=1, v2=4, v3=6, v4=8 w1=1, w2=2, w3=4, w4=6 y=12 请给出在该实例上计算的备忘录表和标记函数表，并说明付钱的方法。