背包查找最大值

我正在学习课程中的prolog，我有一个练习来实现背包问题。我成功地编写了代码，但我无法弄清楚如何从所有可能的解决方案中找到最大的利润。背包查找最大值

下面的代码

between(Lo, Hi, Nu) :- 
    ( integer(Lo), 
     integer(Hi), 
     integer(Nu) 
    -> Nu >= Lo, 
     Nu =< Hi 
    ; integer(Lo), 
     integer(Hi), 
     var(Nu) 
    -> repeat(Lo, Hi, Nu) 
    ). 


add_list(A, [], [A]). 
add_list(A, L, [A|L]). 
add_list([], L, L). 
add_list([H|T], L, L1) :- add(H, L2, L1), add_list(T, L, L2). 


knapsack_go(L, Limit, Amounts, Profit):- 
    knapsack(L, Limit, Amounts, 0, Profit). 
knapsack([], _, _, ProfitSoFar, ProfitSoFar). 
knapsack([Item-Size-Value| Tail], Limit, Amounts, ProfitSoFar, Profit):- 
    Upper is Limit//Size, 
    between(0, Upper, A), 
    Profit2 is (A * Value) + ProfitSoFar, 
    Limit2 is Limit - (A*Size), 
    add_list(A, Amounts2, Amounts), 
    knapsack(Tail, Limit2, Amounts2, Profit2, Profit).

我怎样才能做到最大的利润？

编辑：这是我如何运行它：

knapsack_go([a-7-9, b-11-14, c-19-24], 100, Amounts, Profit).

我想，我问我如何序言生成所有的解决方案，因为现在我得到一个解决方案，我可以在空间压到得到下一个。那么，如何生成所有解决方案，将它们保存在列表中或选择最佳利润。

一些更多的信息 - L是产品尺寸 - 值的列表，限制是在袋子的剩余空间，数量是项目1量，项目2量等

来源

2016-08-24 Infested

如果您的实施为您提供_all_解决方案，但无任何特定顺序，您可以随时收集全部内容，然后挑选出最大值。有关示例，请参见[这里]（http://stackoverflow.com/questions/27317069/collect-all-minimum-solutions-from-a-predicate）。顺便说一句，你似乎正在重写每一个Prolog中都有的谓词（并且已经有几十年了）。 – 2016-08-25 06:39:29

在哪个列表中收集您的解决方案？ – coder

@coder这是'knapsack_go/4'的最后一个参数，我想。问题中应该包含顶层程序的示例调用。 – 2016-08-25 07:19:56

你可以使用的列表：

findall(Profit-Amounts,knapsack_go([a-7-9, b-11-14, c-19-24], 100, Amounts, Profit),L).

这将收集列表L中的所有解决方案，其中L将是表单[Profit-Amounts | T]的列表。现在

，找到最大的利润，你可以写：

max([First | Rest], Result) :- First =FirstP-_ 
    maxC(Rest, First,FirstP, Result). 

    maxC([], Sofar, _, Sofar). 

    maxC([First | Rest], _, Max, Result) :- 
    First = FirstP-_ 
    Max =< FirstP, 
    maxC(Rest, First, FirstP,Result). 

    maxC([First | Rest], Sofar,Max,Result):- 
    First = FirstP-_ 
    Max > FirstP, 
    maxC(Rest, Sofar, Max, Result).

如果你想你会使用上述FirstP-金额的数额列表这将返回的利润最大，其中正处于FirstP-_谓词max，maxC。

来源

2016-08-25 19:26:55 coder

谢谢！我还有一个问题，在我的add_list中，我一次接收[a，b，c]和另一次[a，b，c | _1111] - 为什么会这样呢？ – Infested

@Infested，因为我不确定，因为我无法运行你的代码，因为我使用的是swi-prolog，它不能识别重复的谓词，所以没有运行该程序，我看不到在哪里问题是。 – coder

背包查找最大值

回答

相关问题