2

我正在学习一门课程的序言，我有一个练习来实现背包问题。我成功地编写了代码，但我不知道如何从所有可能的解决方案中找到最大利润。

这是代码

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).

我想我在问如何让 prolog 生成所有解决方案，因为现在我得到了一个解决方案，我可以按下空间来获得下一个解决方案。那么我如何生成所有解决方案，将它们保存在列表或其他东西中并选择最佳利润。

更多信息 - L 是 Item-Size-Value 的列表，Limit 是包中的剩余空间，Amounts 是 Item1 数量、Item2 数量等的列表

4

1 回答 1

2

你可以使用：

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-Amounts 上方使用的金额列表，这将返回利润的最大值，现在谓词 max,maxC 中的 FirstP-_ 是。

于 2016-08-25T19:26:55.710 回答