[问题求解]关于背包问题用贪心算法实现

我这里有一个背包问题需要用Prolog来实现，通过计算profit/weight来对计算出来的结果进行排序，然后将结果（List中的完整内容）打印出来，请问这个问题应该如何完善？我已经做了如下的源代码，先定义了包中内容的变量，然后将包中内容列出来了，E is P/V代表efficiency ratio,P是profit, V是weight（单位为kg）.包的容量为20kg.
跪求Mercury Liao指点

xiayang10 写道:我这里有一个背包问题需要用Prolog来实现，通过计算profit/weight来对计算出来的结果进行排序，然后将结果（List中的完整内容）打印出来，请问这个问题应该如何完善？我已经做了如下的源代码，先定义了包中内容的变量，然后将包中内容列出来了，E is P/V代表efficiency ratio,P是profit, V是weight（单位为kg）.包的容量为20kg.
跪求Mercury Liao指点

% Define the variable for each item
bagContent(N,N1,P,V).

% List of the items in the knapsack
% item number, item name, weight, profit
bagContent(1, 'Kendal Mint Cake',2.44,3.98).
bagContent(2, 'Pith Helmet', 3.97,1.71).
bagContent(3, 'Bread', 4.02,4).
bagContent(4, 'Olive Oil', 1.41,1.55).
bagContent(5, 'Tent', 3.35,3.65).
bagContent(6, 'Firewood', 3.46,1.78).
bagContent(7, 'Water', 1.19,2.7).
bagContent(8, 'Ammunition', 4.64,1.04).
bagContent(9, 'Tinned food', 4.53,3.11).
bagContent(10, 'Weapon', 4.17, 0.2).

% Define the greedy algorithm by calculating efficiency ratio
E is P/V.

不敢…你太客气了。
不晓得有没理解对你的意思，
你是想程序能将所有bagContent的第4个参数除以第3个参数算出E，
然后排序，将排序的结果以bagContent(A,B,C,D)的形式依序print在屏幕上是吗？
（排序是要升序还是降序？）

如果我没理解错的话，这个功能应该非常容易实现。

您好，这个功能正是像您说的这样实现。我用的是SWI-Prolog
代码我只能写到上面所述的那种程度了…唉，能力有限
执行的结果以降序排列，因为这是一个贪心算法的问题啦

程序需要用20KG（背包总重量）减去先算出来的最大价值的物品的重量，然后一直循环不断相减直到20KG被用完
不知道这样您是否可以有明确的思路了，真心希望您能帮我

我现在的问题就是不知道如何在Prolog里思考这个过程。
是要将每个值算出来存到一个临时的空间里，还是怎么的呢？是否需要循环呢？我彻底不知道如何下手。

希望您能帮我完成余下的代码，这个作业搞得我头都大了…
只需用尽可能简单的代码就好了，期待您的回复，以后不懂的我还要请教您！

Mercury Liao 写道:

xiayang10 写道:我这里有一个背包问题需要用Prolog来实现，通过计算profit/weight来对计算出来的结果进行排序，然后将结果（List中的完整内容）打印出来，请问这个问题应该如何完善？我已经做了如下的源代码，先定义了包中内容的变量，然后将包中内容列出来了，E is P/V代表efficiency ratio,P是profit, V是weight（单位为kg）.包的容量为20kg.
跪求Mercury Liao指点

% Define the variable for each item
bagContent(N,N1,P,V).

% List of the items in the knapsack
% item number, item name, weight, profit
bagContent(1, 'Kendal Mint Cake',2.44,3.98).
bagContent(2, 'Pith Helmet', 3.97,1.71).
bagContent(3, 'Bread', 4.02,4).
bagContent(4, 'Olive Oil', 1.41,1.55).
bagContent(5, 'Tent', 3.35,3.65).
bagContent(6, 'Firewood', 3.46,1.78).
bagContent(7, 'Water', 1.19,2.7).
bagContent(8, 'Ammunition', 4.64,1.04).
bagContent(9, 'Tinned food', 4.53,3.11).
bagContent(10, 'Weapon', 4.17, 0.2).

% Define the greedy algorithm by calculating efficiency ratio
E is P/V.

不敢…你太客气了。
不晓得有没理解对你的意思，
你是想程序能将所有bagContent的第4个参数除以第3个参数算出E，
然后排序，将排序的结果以bagContent(A,B,C,D)的形式依序print在屏幕上是吗？
（排序是要升序还是降序？）

如果我没理解错的话，这个功能应该非常容易实现。

你写的"bagContent(N,N1,P,V)."这一句里，第3个参数是profit，
"% item number, item name, weight, profit"这一句里，表明第4个参数是profit，
哪一个是对的？

Mercury Liao 写道:

Mercury Liao 写道:

xiayang10 写道:我这里有一个背包问题需要用Prolog来实现，通过计算profit/weight来对计算出来的结果进行排序，然后将结果（List中的完整内容）打印出来，请问这个问题应该如何完善？我已经做了如下的源代码，先定义了包中内容的变量，然后将包中内容列出来了，E is P/V代表efficiency ratio,P是profit, V是weight（单位为kg）.包的容量为20kg.
跪求Mercury Liao指点

% Define the variable for each item
bagContent(N,N1,P,V).

% List of the items in the knapsack
% item number, item name, weight, profit
bagContent(1, 'Kendal Mint Cake',2.44,3.98).
bagContent(2, 'Pith Helmet', 3.97,1.71).
bagContent(3, 'Bread', 4.02,4).
bagContent(4, 'Olive Oil', 1.41,1.55).
bagContent(5, 'Tent', 3.35,3.65).
bagContent(6, 'Firewood', 3.46,1.78).
bagContent(7, 'Water', 1.19,2.7).
bagContent(8, 'Ammunition', 4.64,1.04).
bagContent(9, 'Tinned food', 4.53,3.11).
bagContent(10, 'Weapon', 4.17, 0.2).

% Define the greedy algorithm by calculating efficiency ratio
E is P/V.

不敢…你太客气了。
不晓得有没理解对你的意思，
你是想程序能将所有bagContent的第4个参数除以第3个参数算出E，
然后排序，将排序的结果以bagContent(A,B,C,D)的形式依序print在屏幕上是吗？
（排序是要升序还是降序？）

如果我没理解错的话，这个功能应该非常容易实现。

你写的"bagContent(N,N1,P,V)."这一句里，第3个参数是profit，
"% item number, item name, weight, profit"这一句里，表明第4个参数是profit，
哪一个是对的？

您好，以这个为准哦：
% item number, item name, weight, profit

xiayang10 写道:您好，这个功能正是像您说的这样实现。我用的是SWI-Prolog
代码我只能写到上面所述的那种程度了…唉，能力有限
执行的结果以降序排列，因为这是一个贪心算法的问题啦

程序需要用20KG（背包总重量）减去先算出来的最大价值的物品的重量，然后一直循环不断相减直到20KG被用完
不知道这样您是否可以有明确的思路了，真心希望您能帮我

我现在的问题就是不知道如何在Prolog里思考这个过程。
是要将每个值算出来存到一个临时的空间里，还是怎么的呢？是否需要循环呢？我彻底不知道如何下手。

希望您能帮我完成余下的代码，这个作业搞得我头都大了…
只需用尽可能简单的代码就好了，期待您的回复，以后不懂的我还要请教您！

我先假设你写错了，其实是bagContent(N,N1,V,P)，那么代码如下：
（假如我V跟P搞反了，你把所有bagContent参数里的V跟P交换就行。）

代码:

% Define the variable for each item
% bagContent(N,N1,V,P).

% List of the items in the knapsack
% item number, item name, weight, profit
bagContent(1, 'Kendal Mint Cake',2.44,3.98).
bagContent(2, 'Pith Helmet', 3.97,1.71).
bagContent(3, 'Bread', 4.02,4).
bagContent(4, 'Olive Oil', 1.41,1.55).
bagContent(5, 'Tent', 3.35,3.65).
bagContent(6, 'Firewood', 3.46,1.78).
bagContent(7, 'Water', 1.19,2.7).
bagContent(8, 'Ammunition', 4.64,1.04).
bagContent(9, 'Tinned food', 4.53,3.11).
bagContent(10, 'Weapon', 4.17, 0.2).

% Define the greedy algorithm by calculating efficiency ratio
% E is P/V

%%%%%%%
calculate_E(E-N-V) :- bagContent(N, N1, V, P), E is P / V.

bag :-
  findall(E-N-V, calculate_E(E-N-V), E_list), sort(E_list, List), reverse(List, L),
  print_bagContent(L, 0).

print_bagContent(L, Weight) :-
  L = [H|T], H = E-N-V, New_Weight is Weight + V,
  New_Weight =< 20, bagContent(N, N1, V, P), write(bagContent(N, N1, V, P)), nl,
  print_bagContent(T, New_Weight).

?- bag.
bagContent(7,Water,1.19,2.7)
bagContent(1,Kendal Mint Cake,2.44,3.98)
bagContent(4,Olive Oil,1.41,1.55)
bagContent(5,Tent,3.35,3.65)
bagContent(3,Bread,4.02,4)
bagContent(9,Tinned food,4.53,3.11)
false.

Mercury Liao 写道:

xiayang10 写道:您好，这个功能正是像您说的这样实现。我用的是SWI-Prolog
代码我只能写到上面所述的那种程度了…唉，能力有限
执行的结果以降序排列，因为这是一个贪心算法的问题啦

程序需要用20KG（背包总重量）减去先算出来的最大价值的物品的重量，然后一直循环不断相减直到20KG被用完
不知道这样您是否可以有明确的思路了，真心希望您能帮我

我现在的问题就是不知道如何在Prolog里思考这个过程。
是要将每个值算出来存到一个临时的空间里，还是怎么的呢？是否需要循环呢？我彻底不知道如何下手。

希望您能帮我完成余下的代码，这个作业搞得我头都大了…
只需用尽可能简单的代码就好了，期待您的回复，以后不懂的我还要请教您！

我先假设你写错了，其实是bagContent(N,N1,V,P)，那么代码如下：
（假如我V跟P搞反了，你把所有bagContent参数里的V跟P交换就行。）

代码:

% Define the variable for each item
% bagContent(N,N1,V,P).

% List of the items in the knapsack
% item number, item name, weight, profit
bagContent(1, 'Kendal Mint Cake',2.44,3.98).
bagContent(2, 'Pith Helmet', 3.97,1.71).
bagContent(3, 'Bread', 4.02,4).
bagContent(4, 'Olive Oil', 1.41,1.55).
bagContent(5, 'Tent', 3.35,3.65).
bagContent(6, 'Firewood', 3.46,1.78).
bagContent(7, 'Water', 1.19,2.7).
bagContent(8, 'Ammunition', 4.64,1.04).
bagContent(9, 'Tinned food', 4.53,3.11).
bagContent(10, 'Weapon', 4.17, 0.2).

% Define the greedy algorithm by calculating efficiency ratio
% E is P/V

%%%%%%%
calculate_E(E-N-V) :- bagContent(N, N1, V, P), E is P / V.

bag :-
  findall(E-N-V, calculate_E(E-N-V), E_list), sort(E_list, List), reverse(List, L),
  print_bagContent(L, 0).

print_bagContent(L, Weight) :-
  L = [H|T], H = E-N-V, New_Weight is Weight + V,
  New_Weight =< 20, bagContent(N, N1, V, P), write(bagContent(N, N1, V, P)), nl,
  print_bagContent(T, New_Weight).

?- bag.
bagContent(7,Water,1.19,2.7)
bagContent(1,Kendal Mint Cake,2.44,3.98)
bagContent(4,Olive Oil,1.41,1.55)
bagContent(5,Tent,3.35,3.65)
bagContent(3,Bread,4.02,4)
bagContent(9,Tinned food,4.53,3.11)
false.

非常感谢您的回复，不过我刚看了一下代码，有些地方不是很明白哦。因为我对Prolog很不熟悉，只会一些很简单的推导而已。

calculate_E(E-N-V) ，这一句是什么意思呢？我知道是计算效率的过程，但是括号里面的三个用横杠连接起来的东西代表着什么？然后下面有三个print_bagContent，具体哪一个是用于输出最后的结果呢？请问是否可以在您最后几行代码的适当地方加入一些注释？因为我还是需要理解一下这个程序的，谢谢啦！

xiayang10 写道:

Mercury Liao 写道:

xiayang10 写道:您好，这个功能正是像您说的这样实现。我用的是SWI-Prolog
代码我只能写到上面所述的那种程度了…唉，能力有限
执行的结果以降序排列，因为这是一个贪心算法的问题啦

程序需要用20KG（背包总重量）减去先算出来的最大价值的物品的重量，然后一直循环不断相减直到20KG被用完
不知道这样您是否可以有明确的思路了，真心希望您能帮我

我现在的问题就是不知道如何在Prolog里思考这个过程。
是要将每个值算出来存到一个临时的空间里，还是怎么的呢？是否需要循环呢？我彻底不知道如何下手。

希望您能帮我完成余下的代码，这个作业搞得我头都大了…
只需用尽可能简单的代码就好了，期待您的回复，以后不懂的我还要请教您！

我先假设你写错了，其实是bagContent(N,N1,V,P)，那么代码如下：
（假如我V跟P搞反了，你把所有bagContent参数里的V跟P交换就行。）

代码:

% Define the variable for each item
% bagContent(N,N1,V,P).

% List of the items in the knapsack
% item number, item name, weight, profit
bagContent(1, 'Kendal Mint Cake',2.44,3.98).
bagContent(2, 'Pith Helmet', 3.97,1.71).
bagContent(3, 'Bread', 4.02,4).
bagContent(4, 'Olive Oil', 1.41,1.55).
bagContent(5, 'Tent', 3.35,3.65).
bagContent(6, 'Firewood', 3.46,1.78).
bagContent(7, 'Water', 1.19,2.7).
bagContent(8, 'Ammunition', 4.64,1.04).
bagContent(9, 'Tinned food', 4.53,3.11).
bagContent(10, 'Weapon', 4.17, 0.2).

% Define the greedy algorithm by calculating efficiency ratio
% E is P/V

%%%%%%%
calculate_E(E-N-V) :- bagContent(N, N1, V, P), E is P / V.

bag :-
  findall(E-N-V, calculate_E(E-N-V), E_list), sort(E_list, List), reverse(List, L),
  print_bagContent(L, 0).

print_bagContent(L, Weight) :-
  L = [H|T], H = E-N-V, New_Weight is Weight + V,
  New_Weight =< 20, bagContent(N, N1, V, P), write(bagContent(N, N1, V, P)), nl,
  print_bagContent(T, New_Weight).

?- bag.
bagContent(7,Water,1.19,2.7)
bagContent(1,Kendal Mint Cake,2.44,3.98)
bagContent(4,Olive Oil,1.41,1.55)
bagContent(5,Tent,3.35,3.65)
bagContent(3,Bread,4.02,4)
bagContent(9,Tinned food,4.53,3.11)
false.

非常感谢您的回复，不过我刚看了一下代码，有些地方不是很明白哦。因为我对Prolog很不熟悉，只会一些很简单的推导而已。

calculate_E(E-N-V) ，这一句是什么意思呢？我知道是计算效率的过程，但是括号里面的三个用横杠连接起来的东西代表着什么？然后下面有三个print_bagContent，具体哪一个是用于输出最后的结果呢？请问是否可以在您最后几行代码的适当地方加入一些注释？因为我还是需要理解一下这个程序的，谢谢啦！

代码:


%prolog里的+, -, *, /可以用来连接变量，把相关的变量"黏"在一起变成一个新变量，方便我们同时移动这些变量。
%比如 People = ID+Name+Age+Country，将ID等4个变量连在一起变成一个新变量People，以后你用People = A+B+C+D，
%就能将身份证号指定给A，姓名指定给B……依此类推。
%这句主要就是算出所有bagContent的E，然后把E、编号、weight信息由E-N-V传回。
calculate_E(E-N-V) :- bagContent(N, N1, V, P), E is P / V.

%findall解出所有满足calculate_E的解，将满足的解装进E_list。
%sort将E_list的内容升序排序，将结果输出在List。
%因为E-N-V的首变量是E，所以E的大小会直接影响其排序后的位置，所以其实sort就是依据E排序。
%reverse将List逆序排列，并输出至L。所以L现在是降序排列了。
%调用print_bagContent过程，过程如下段定义。
%第1个参数给L，把我们总共有哪些可选的bagContent（以降序方式）传进去；第2个参数给0是表示一开始我们背包里的重量是0。
bag :-
  findall(E-N-V, calculate_E(E-N-V), E_list), sort(E_list, List), reverse(List, L),
  print_bagContent(L, 0).

%L=[H|T]表示L的第一项指定给H，余下的List指定给T
%H = E-N-V不用介绍了吧？就是把H的信息读出来分别指派给3个变量。
%New_Weight用来表示如果装进这个物品，我们的背包重量变成多少。
%检查装进后的背包重量是否不超过20，是的话才继续执行后面的代码，否则传回false结束程序。
%利用已知的N、V，去匹配符合的bagContent(N, N1, V, P)。
%真正将bagContent输出的命令是write，然后nl是换行（new line）。
%最后一句print_bagContent是调用自己（递归），意思就是重复做同样的事，
%只不过这次传入的第1个参数是T（扣掉H后的可选bagContent），
%传入的第2个参数是New_Weight，因为你的背包已经装入了New_Weight重的东西了。
print_bagContent(L, Weight) :-
  L = [H|T], H = E-N-V, New_Weight is Weight + V,
  New_Weight =< 20, bagContent(N, N1, V, P), write(bagContent(N, N1, V, P)), nl,
  print_bagContent(T, New_Weight).

太感谢了！我先研究研究！

你好，看了你的代码和注解真的受益匪浅，再次感谢！

我后来参考了网上的一些代码，自己用Python解了一下这个程序，以下是我的代码，不知道你懂不懂Python，如果懂的话帮我看看。

我貌似解出来以后，运算结果和Prolog的有点不一样，你帮我看下是怎么回事，我算出来正好20呢？

Knapsack = 20.00

items = [
(1, "1", 2.44, 3.98),
(2, "2", 3.97, 1.71),
(3, "3", 4.02, 4),
(4, "4", 1.41, 1.55),
(5, "5", 3.35, 3.65),
(6, "6", 3.46, 1.78),
(7, "7", 1.19, 2.7),
(8, "8", 4.64, 1.04),
(9, "9", 4.53, 3.11),
(10, "10", 4.17, 0.2) ]

AfterSorted = sorted(((profit/ItemWeight, ItemWeight, ItemName)
for itemno, ItemName, ItemWeight, profit in items), reverse = True)
Weight = Value = 0
Knapsacked = []
for unit_Valueue, ItemWeight, ItemName in AfterSorted:


portion = min(Knapsack - Weight, ItemWeight)
Weight += portion
addValue = portion * unit_Valueue
Value += addValue
Knapsacked += [(ItemName, portion, addValue)]

if Weight >= Knapsack:
break

print(" Item Name ItemWeight Profit")
print("\n".join("%13s %20.2f %16.2f" % item for item in Knapsacked))
print("\nItemWeight in total: %5.2f\nValueue in total: %5.2f" % (Weight, Value))


另外不知道你是否懂Haskell，我还需要用Haskell来解这个程序，同样的算法，哎，实在是没头绪

xiayang10 写道:你好，看了你的代码和注解真的受益匪浅，再次感谢！

我后来参考了网上的一些代码，自己用Python解了一下这个程序，以下是我的代码，不知道你懂不懂Python，如果懂的话帮我看看。

我貌似解出来以后，运算结果和Prolog的有点不一样，你帮我看下是怎么回事，我算出来正好20呢？

Knapsack = 20.00

items = [
(1, "1", 2.44, 3.98),
(2, "2", 3.97, 1.71),
(3, "3", 4.02, 4),
(4, "4", 1.41, 1.55),
(5, "5", 3.35, 3.65),
(6, "6", 3.46, 1.78),
(7, "7", 1.19, 2.7),
(8, "8", 4.64, 1.04),
(9, "9", 4.53, 3.11),
(10, "10", 4.17, 0.2) ]

AfterSorted = sorted(((profit/ItemWeight, ItemWeight, ItemName)
for itemno, ItemName, ItemWeight, profit in items), reverse = True)
Weight = Value = 0
Knapsacked = []
for unit_Valueue, ItemWeight, ItemName in AfterSorted:


portion = min(Knapsack - Weight, ItemWeight)
Weight += portion
addValue = portion * unit_Valueue
Value += addValue
Knapsacked += [(ItemName, portion, addValue)]

if Weight >= Knapsack:
break

print(" Item Name ItemWeight Profit")
print("\n".join("%13s %20.2f %16.2f" % item for item in Knapsacked))
print("\nItemWeight in total: %5.2f\nValueue in total: %5.2f" % (Weight, Value))


另外不知道你是否懂Haskell，我还需要用Haskell来解这个程序，同样的算法，哎，实在是没头绪

我没学过Python，不过我还是试着看了一下，
"portion = min(Knapsack - Weight, ItemWeight)"这句不太明白，
为什么要取这两者的较小值？

比如说按照我用prolog跑出的结果可知，装完编号为9的物品后，
背包重量已经达到16.94，
而下一个E较大的是编号6的物品，但重量为3.46，
很明显加上去的话一定会超过20，
但你这句的写法（如果我没理解错），取Knapsack - Weight与ItemWeight的较小值，
前者应该是剩余容量吧？也就是20-16.94=3.06，后者是3.46，
取小的值就是取3.06，然后你下一句"Weight += portion"又把portion加进Weight，
那肯定最后Weight刚好等于20的啊！

xiayang10 写道:你好，看了你的代码和注解真的受益匪浅，再次感谢！

我后来参考了网上的一些代码，自己用Python解了一下这个程序，以下是我的代码，不知道你懂不懂Python，如果懂的话帮我看看。

我貌似解出来以后，运算结果和Prolog的有点不一样，你帮我看下是怎么回事，我算出来正好20呢？

Knapsack = 20.00

items = [
(1, "1", 2.44, 3.98),
(2, "2", 3.97, 1.71),
(3, "3", 4.02, 4),
(4, "4", 1.41, 1.55),
(5, "5", 3.35, 3.65),
(6, "6", 3.46, 1.78),
(7, "7", 1.19, 2.7),
(8, "8", 4.64, 1.04),
(9, "9", 4.53, 3.11),
(10, "10", 4.17, 0.2) ]

AfterSorted = sorted(((profit/ItemWeight, ItemWeight, ItemName)
for itemno, ItemName, ItemWeight, profit in items), reverse = True)
Weight = Value = 0
Knapsacked = []
for unit_Valueue, ItemWeight, ItemName in AfterSorted:


portion = min(Knapsack - Weight, ItemWeight)
Weight += portion
addValue = portion * unit_Valueue
Value += addValue
Knapsacked += [(ItemName, portion, addValue)]

if Weight >= Knapsack:
break

print(" Item Name ItemWeight Profit")
print("\n".join("%13s %20.2f %16.2f" % item for item in Knapsacked))
print("\nItemWeight in total: %5.2f\nValueue in total: %5.2f" % (Weight, Value))


另外不知道你是否懂Haskell，我还需要用Haskell来解这个程序，同样的算法，哎，实在是没头绪

这题目可以容许只装一件物品的一部分进背包吗？
如果可以的话，那确实应该刚好是20，
我看你写portion取两者较小值，猜想你是否想表达这个意思？

感谢你的指点，这个代码我是看了网上的一些资料才拼凑起来好不容易可以用的，呵呵。
后来我已经自己把这个代码经过你的提示进行了修正，现在完美了

没错，正是你之前说的那个意思，最后结果必须是16.9KG才行

另外我现在还有一个问题，就是如何用分支界限算法去解那个同样的Prolog背包问题...

这个我觉得肯定会非常难吧

但是我想知道大概的思路是怎么回事，好像是说10个物品里可以在前六个物品（之前排序好的六个物品）设置一个断点

1 2 3 4 5 6 / 7 8 9 10 （已经根据Profit排好序的10个物品）

因为前面六个物品加起来是16.9KG，肯定不足20KG，那么就在断点后面尝试去抓一个最大的，如果抓到了，然后把断点继续往后面移动，继续找，直到直到选出一个能让背包接近其20KG限制的一个物品，进一步获得最大的利益，请问您是否可以根据这个问题帮我详细分析一下这个算法？如果可以，能否提供一下Prolog的解法？

我的算法很差劲，以前根本就没有学过算法类的东西，唉。

xiayang10 写道:感谢你的指点，这个代码我是看了网上的一些资料才拼凑起来好不容易可以用的，呵呵。
后来我已经自己把这个代码经过你的提示进行了修正，现在完美了

没错，正是你之前说的那个意思，最后结果必须是16.9KG才行

另外我现在还有一个问题，就是如何用分支界限算法去解那个同样的Prolog背包问题...

这个我觉得肯定会非常难吧

但是我想知道大概的思路是怎么回事，好像是说10个物品里可以在前六个物品（之前排序好的六个物品）设置一个断点

1 2 3 4 5 6 / 7 8 9 10 （已经根据Profit排好序的10个物品）

因为前面六个物品加起来是16.9KG，肯定不足20KG，那么就在断点后面尝试去抓一个最大的，如果抓到了，然后把断点继续往后面移动，继续找，直到直到选出一个能让背包接近其20KG限制的一个物品，进一步获得最大的利益，请问您是否可以根据这个问题帮我详细分析一下这个算法？如果可以，能否提供一下Prolog的解法？

我的算法很差劲，以前根本就没有学过算法类的东西，唉。

我先确定一下分支界限是什么意思，
是不是指有好几个界限，比如12、16、20，
然后如果一开始装到重量达11.5，下一个是0.7，加起来超过12，
就输出/表示先装成一小包，0.7并入下一包？
我随便举个例问的，主要是想你描述一下分支界限怎么定义，
免得我搞错题意了。

Mercury Liao 写道:

xiayang10 写道:感谢你的指点，这个代码我是看了网上的一些资料才拼凑起来好不容易可以用的，呵呵。
后来我已经自己把这个代码经过你的提示进行了修正，现在完美了

没错，正是你之前说的那个意思，最后结果必须是16.9KG才行

另外我现在还有一个问题，就是如何用分支界限算法去解那个同样的Prolog背包问题...

这个我觉得肯定会非常难吧

但是我想知道大概的思路是怎么回事，好像是说10个物品里可以在前六个物品（之前排序好的六个物品）设置一个断点

1 2 3 4 5 6 / 7 8 9 10 （已经根据Profit排好序的10个物品）

因为前面六个物品加起来是16.9KG，肯定不足20KG，那么就在断点后面尝试去抓一个最大的，如果抓到了，然后把断点继续往后面移动，继续找，直到直到选出一个能让背包接近其20KG限制的一个物品，进一步获得最大的利益，请问您是否可以根据这个问题帮我详细分析一下这个算法？如果可以，能否提供一下Prolog的解法？

我的算法很差劲，以前根本就没有学过算法类的东西，唉。

我先确定一下分支界限是什么意思，
是不是指有好几个界限，比如12、16、20，
然后如果一开始装到重量达11.5，下一个是0.7，加起来超过12，
就输出/表示先装成一小包，0.7并入下一包？
我随便举个例问的，主要是想你描述一下分支界限怎么定义，
免得我搞错题意了。

说实话这个如何定义的我也不清楚，因为我没有上过系统化的算法课，我们老师的讲法是先把背包中的东西按照性价比排序
然后得出一个列表，因为我们之前用贪心算法选出了六个东西，所以在前六个最有性价比的东西后设置断点
然后往第七个物品上测试，如果会塞爆背包，则放弃７，测试８，如果８可以，则把断点移动到８上，再往９上面测试

就设置一个界限就好，这个程序我估计会比较难解吧…对我来说基本是不可能的，尤其是对于Prolog这门语言来说，太高深了吧…

xiayang10 写道:

Mercury Liao 写道:

xiayang10 写道:感谢你的指点，这个代码我是看了网上的一些资料才拼凑起来好不容易可以用的，呵呵。
后来我已经自己把这个代码经过你的提示进行了修正，现在完美了

没错，正是你之前说的那个意思，最后结果必须是16.9KG才行

另外我现在还有一个问题，就是如何用分支界限算法去解那个同样的Prolog背包问题...

这个我觉得肯定会非常难吧

但是我想知道大概的思路是怎么回事，好像是说10个物品里可以在前六个物品（之前排序好的六个物品）设置一个断点

1 2 3 4 5 6 / 7 8 9 10 （已经根据Profit排好序的10个物品）

因为前面六个物品加起来是16.9KG，肯定不足20KG，那么就在断点后面尝试去抓一个最大的，如果抓到了，然后把断点继续往后面移动，继续找，直到直到选出一个能让背包接近其20KG限制的一个物品，进一步获得最大的利益，请问您是否可以根据这个问题帮我详细分析一下这个算法？如果可以，能否提供一下Prolog的解法？

我的算法很差劲，以前根本就没有学过算法类的东西，唉。

我先确定一下分支界限是什么意思，
是不是指有好几个界限，比如12、16、20，
然后如果一开始装到重量达11.5，下一个是0.7，加起来超过12，
就输出/表示先装成一小包，0.7并入下一包？
我随便举个例问的，主要是想你描述一下分支界限怎么定义，
免得我搞错题意了。

说实话这个如何定义的我也不清楚，因为我没有上过系统化的算法课，我们老师的讲法是先把背包中的东西按照性价比排序
然后得出一个列表，因为我们之前用贪心算法选出了六个东西，所以在前六个最有性价比的东西后设置断点
然后往第七个物品上测试，如果会塞爆背包，则放弃７，测试８，如果８可以，则把断点移动到８上，再往９上面测试

就设置一个界限就好，这个程序我估计会比较难解吧…对我来说基本是不可能的，尤其是对于Prolog这门语言来说，太高深了吧…

不会很难啊，你把原代码最后一段稍微改一下成这样就行了：

代码:

print_bagContent(L, Weight) :-
  L = [H|T], H = E-N-V, New_Weight is Weight + V,
  ( New_Weight =< 20 -> bagContent(N, N1, V, P), write(bagContent(N, N1, V, P)), nl, print_bagContent(T, New_Weight);
  print_bagContent(T, Weight)).

根据你原本背包内容的设定，结果还是跟原本一样。
但如果你把编号10改成bagContent(10, 'Weapon', 0.1, 0.0001)，
运行结果就变成：

30 ?- bag.
bagContent(7,Water,1.19,2.7)
bagContent(1,Kendal Mint Cake,2.44,3.98)
bagContent(4,Olive Oil,1.41,1.55)
bagContent(5,Tent,3.35,3.65)
bagContent(3,Bread,4.02,4)
bagContent(9,Tinned food,4.53,3.11)
bagContent(10,Weapon,0.1,0.0001)
false.

也就是说，虽然编号10的E很小很小（排序在很后面），
但是因为背包还装得下它，所以还是把它装进去了。

那若不按我之前的思路来，假设断点不用设置在第六个物品上呢？主要是不知道这样的原理用Prolog如何去描述了

另外还有就是，如何在SWI-Prolog里知道执行一个查询所需的时间？要特别精确的那种。可以做到吗？谢谢了！

xiayang10 写道:那若不按我之前的思路来，假设断点不用设置在第六个物品上呢？主要是不知道这样的原理用Prolog如何去描述了

另外还有就是，如何在SWI-Prolog里知道执行一个查询所需的时间？要特别精确的那种。可以做到吗？谢谢了！

之前我写的代码没有一个是在第6个物品上设断点啊！
都只是判断重量有无超过20，不是很明白你说的第6个物品设断点是什么意思。

关于执行时间的问题，你可以在执行的时候加一个time谓词，如：

8 ?- time(bag).
bagContent(7,Water,1.19,2.7)
bagContent(1,Kendal Mint Cake,2.44,3.98)
bagContent(4,Olive Oil,1.41,1.55)
bagContent(5,Tent,3.35,3.65)
bagContent(3,Bread,4.02,4)
bagContent(9,Tinned food,4.53,3.11)
% 100 inferences, 0.000 CPU in 0.234 seconds (0% CPU, Infinite Lips)
false.

里面就有标明花了0.234秒的时间。

居然用prolog求解规划问题，还要是np完全问题，太有才了。。。= =!!