Maison >développement back-end >tutoriel php >求哪几个数字之和接近某一个给定的值(小于等于)

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

WBOY
WBOYoriginal
2016-07-06 13:53:551546parcourir

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

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

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

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

回复内容:

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

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

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

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

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

01背包问题

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

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn