算法基础–优惠券问题(贪心算法)

算法基础–优惠券问题(贪心算法)

近期某商场由于周年庆,开启了“0元购”活动。活动中,消费者可以通过组合手中的代金券,实现0元购买指定商品。

聪明的小团想要用算法来帮助他快速计算:对于指定价格的商品,使用代金券凑出其价格即可,但所使用的代金券总面额不可超过商品价格。由于代金券数量有限,使用较少的代金券张数则可以实现价值最大化,即最佳优惠。

假设现有100元的商品,而代金券有50元、30元、20元、5元四种,则最佳优惠是两张50元面额的代金券;而如果现有65元的商品,则最佳优惠是两张30元代金券以及一张5元代金券。

请你帮助小团使用一段代码来实现代金券计算。
输入描述:

多组输入输出,读到s=0时结束 输入可以有多个测试样例,每个测试由两行组成。
其中第一行包含一个整数P,表示商品的价格,1≤P≤10000;输入P为0时表示结束。
第二行包含若干整数,使用空格分割。其中第一个整数N(1≤N≤20)表示有多少种代金券,其后跟随M个整数,表示手中持有的代金券面额(1≤N≤1000),每种代金券数量不限。

输出描述:

找到最少张数的代金券,使其面额恰好等于商品价格。输出所使用的代金券数量;
如果有多个最优解,只输出其中一种即可;
如果无解,则需输出“Impossible”。

贪心算法的含义我就不去总结了。毕竟自己也不太理解到位。但在这个例子中我明白了解题的思路。分享给大家,大家结合别人的贪心算法总结一起使用吧。
话不多说,先给代码:

 var num = 65;  var type = 4;  var money = [50,30,20,5];  function getResult(num, type, money) { var dp = []; dp[0] = 0; for(var i=1;i<=num;i++){ var arr = []; for(var j=0;j<money.length;j++){ if(i>=money[j]){  arr.push(dp[i-money[j]] + 1);  } } dp[i] = Math.min(...arr); } return dp[num] === Infinity?"Impossible":dp[num]; } 

分析
arr数组的值存储的是每一个代金券可搭配的金额的代金券种类:

1 [ ] 2 [ ] 3 [ ] 4 [ ] 5 [ 1 ] 10 [ 2 ] 15 [ 3 ] 20 [ 1 ] 20 [ 1, 4 ] 25 [ 2 ] 25 [ 2, 2 ] 30 [ 1 ] 30 [ 1, 3 ] 30 [ 1, 3, 3 ] 35 [ 2 ] 35 [ 2, 4 ] 35 [ 2, 4, 2 ] 40 [ 3 ] 40 [ 3, 2 ] 40 [ 3, 2, 3 ] 45 [ 4 ] 45 [ 4, 3 ] 45 [ 4, 3, 3 ] 50 [ 1 ] 50 [ 1, 2 ] 50 [ 1, 2, 2 ] 50 [ 1, 2, 2, 4 ] 55 [ 2 ] 55 [ 2, 3 ] 55 [ 2, 3, 3 ] 55 [ 2, 3, 3, 2 ] 60 [ 3 ] 60 [ 3, 2 ] 60 [ 3, 2, 3 ] 60 [ 3, 2, 3, 3 ] 65 [ 4 ] 65 [ 4, 3 ] 65 [ 4, 3, 4 ] 65 [ 4, 3, 4, 3 ] 

dp数组会存储每一个<=65的数值的代金券搭配的数目的最小值。如果为Infinity则输出Impossible。在本例中,dp数组的值:

dp[1]: Infinity dp[2]: Infinity dp[3]: Infinity dp[4]: Infinity dp[5]: 1 dp[6]: Infinity dp[7]: Infinity dp[8]: Infinity dp[9]: Infinity dp[10]: 2 dp[11]: Infinity dp[12]: Infinity dp[13]: Infinity dp[14]: Infinity dp[15]: 3 dp[16]: Infinity dp[17]: Infinity dp[18]: Infinity dp[19]: Infinity dp[20]: 1 dp[21]: Infinity dp[22]: Infinity dp[23]: Infinity dp[24]: Infinity dp[25]: 2 dp[26]: Infinity dp[27]: Infinity dp[28]: Infinity dp[29]: Infinity dp[30]: 1 dp[31]: Infinity dp[32]: Infinity dp[33]: Infinity dp[34]: Infinity dp[35]: 2 dp[36]: Infinity dp[37]: Infinity dp[38]: Infinity dp[39]: Infinity dp[40]: 2 dp[41]: Infinity dp[42]: Infinity dp[43]: Infinity dp[44]: Infinity dp[45]: 3 dp[46]: Infinity dp[47]: Infinity dp[48]: Infinity dp[49]: Infinity dp[50]: 1 dp[51]: Infinity dp[52]: Infinity dp[53]: Infinity dp[54]: Infinity dp[55]: 2 dp[56]: Infinity dp[57]: Infinity dp[58]: Infinity dp[59]: Infinity dp[60]: 2 dp[61]: Infinity dp[62]: Infinity dp[63]: Infinity dp[64]: Infinity dp[65]: 3 
 if (i >= money[j]) {  arr.push(dp[i - money[j]] + 1);  }  

这样说就基本清楚了。
说的很简陋,主要看代码,和输出结果分析。主要思想就是‘大事化小,小事化了

原文链接:https://blog.csdn.net/nmsl_double/article/details/109511300?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165277499316782184681137%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=165277499316782184681137&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-23-109511300-null-null.nonecase&utm_term=%E4%BC%98%E6%83%A0

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
文明发言,共建和谐米科社区
提交
头像

昵称

取消
昵称表情图片