Heim  >  Artikel  >  Backend-Entwicklung  >  求哪几个数字之和接近某一个给定的值(小于等于)

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

WBOY
WBOYOriginal
2016-07-06 13:53:551523Durchsuche

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

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

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

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

回复内容:

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

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

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

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

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

01背包问题

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

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn