继续上一个动态最优解。
现实中背包里的道具数量有限，此时我们需要增加道具数量的限定，只需要在子问题的有效解上做限制就好了。
说明：当数量超过了，我们就不认为这是个有效解。
假如限制如下：
分析运行结果：60 的时候最优解不再是两个30 ，而是6个5+1个30
当所有道具都用完了也不会有问题（可优化，提前判断下n是不是已经大于所有道具的组合了）
lua实现源码：
function __Class:myTest(num)
local cost = {5,21,7,30} --道具表
self:botton_up_cut(cost,91) -- 91：目标
end
function __Class:botton_up_cut(p,n)
local count = 0 --循环次数
local r={}
table.sort(p,function ( a,b ) --希望大道具优先使用对道具表从大到小排序
return a>b
end)
local item = {} --具体的道具使用情况表
for j=0,n do
item[j]={}
for i,v in ipairs(p) do
item[j][v] = 0
end
end
r[0] = 0;
local q;
for j=1,n do
q= r[j-1]>0 and r[j-1] or 9999999 --当前找到的最优解
item[j] = r[j-1]>0 and clone(item[j-1]) or item[j] --当前最优解的道具组合
for k,w in ipairs(p) do --遍历道具列表（从时长最大的道具开始）
local num = j-p[1] >=0 and p[1] or j
for i=1,num do --遍历之前的最优解（优化：只用遍历到j-最大道具就可以了）
local t1 = q-j -- 当前最优解下浪费的时间，小于0 我们认为不是有效解
local t2 = w+r[j-i]-j -- 前一个最优解下浪费的时间
count = count+1
if t1 <0 and t2 >=0 then
if item[j-i][w]+1 <= self:getItemCount(w) then --限制道具数量
q = w+r[j-i] --找到一个有效解
item[j] = clone(item[j-i])
item[j][w]= item[j][w]+1
if q-j <=0 then --新的有效解已经是最优，break掉
break
end
end
end
if t1>=0 and t2 >=0 then
if t1>t2 and item[j-i][w]+1 <= self:getItemCount(w) then --限制道具数量
-- if t1>t2 then --两个都是有效解的情况下，取最小的有效解(不限制道具数量)
item[j] = clone(item[j-i])
item[j][w]= item[j][w]+1
q = w+r[j-i]
end
if q-j <=0 then
break
end
end
end
if q-j <=0 then --从大到小遍历的，大的都不满足条件了，小的就不用看了
break
end
end
r[j] = q;
print("目标n==="..j.." 最优解r====="..r[j].." 循环次数circle count:"..count.."\n:组合情况")
dump(item[j])
end
return q
end
function __Class:getItemCount(item)
local tmp= {
[5]=7,
[7]=2,
[21] = 0,
[30]= 1
}
return tmp[item]
end
网友评论