求一个算法，从一个数组（如 [13,11,10,9,6,5,4,3,2,1] ）中，找出多个数，使这些数的和是一个定值（如 40），数可以重复使用

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3757 天前的主题，其中的信息可能已经有所发展或是发生改变。

其实就是会员购买了 40 元的零食盒，现在我根据他的喜好找出来了一些零食，这些零食的价格组成了一个数组，现在需要从这些零食中挑选一些出来组成一盒零食。

第 1 条附言 · 2014-08-09 16:12:37 +08:00

感谢大家！

另外再回答 @pimin 的疑问
在得到这个数组之前我已经做了很多处理了，主要考虑的因素是：
1、他喜欢吃的零食的其他也喜欢吃的会员们喜欢吃的零食（好绕口）
2、他不喜欢吃的零食的其他会员们也不喜欢吃的零食
3、他喜欢吃的零食的其他类似零食

最终得到了一些零食，这些零食有各种价格，我对这些价格取整并去重之后，得到了题中的数组。

数组

零食

组成

15 条回复 • 2014-08-16 17:24:04 +08:00

bcxx

2014-08-09 15:08:14 +08:00

背包啊……

wong2

2014-08-09 15:09:22 +08:00

啊，看到了算法在日常中的使用~

QuakeX

2014-08-09 15:15:26 +08:00

背包啊

XadillaX

2014-08-09 15:44:02 +08:00

而且是无限背包 -。 -

canesten

2014-08-09 15:45:55 +08:00

lua实现：

local price = {13,11,10,9,6,5,4,3,2,1}

local balance = 40

function randomFood()
math.randomseed(os.time())
math.random(100)
math.random(100)
math.random(100)
math.random(100)
local result = {}
local num = #price
while balance > 0 do
local rangeLeft = 0
for i = 1, num do
if price[i] <= balance then
rangeLeft = i
break
end
end
if rangeLeft == 0 then
break
end
local randomIndex = math.random(rangeLeft, num)
local randomPrice = price[randomIndex]
balance = balance - randomPrice
table.insert(result, randomPrice)
print(randomPrice)
end
print(balance)
end

randomFood()

楼主拿去玩

canesten

2014-08-09 15:47:44 +08:00

没了缩进好丑
不过脚本语言无所谓了
楼主拿去跑就是了