求哪几个数字之和接近某一个给定的值(小于等于)

生活中,经常会有这样一个情况:

网上购物,一张固定的购物券1000,有很多商品,单价不同,101,230,330,210,299,…
怎样才能尽可能的使用完这1000元。

这只是一个例子,具体转换成计算机专业的描述我不知道该怎么表达,
如题:求哪几个数字之和接近某一个给定的值(小于等于)

这样一个业务逻辑,该用怎样的算法呢?不限语言。(c,php,java,node)

这种问题属于背包问题范畴,可采用贪心算法进行解决。

01背包问题

这是典型的01背包问题,最常见的是用动态规划解决

发表评论

电子邮件地址不会被公开。 必填项已用*标注