因为以后可能要用到，于是今天用 Erlang 写了一个 0-1 背包算法，这算是我第一次用 Erlang 写算法，也是我第二次写 Erlang 程序……
以前都使用正常语言写，各种算法自然不会难写。所谓正常的语言，呃……也就是我们平时用的最多的语言了，像 C++、Python 什么的在我看来都还算正常的语言。那么 Erlang 到底哪里不正常了呢？
其实 Erlang 只要两个不正常的地方就足够囧死人了……那就是：
- 没有循环，必须用递归代替
- 数组不能随机访问，只能从头部读写
其实说数组不能随机访问吧，应该也是能的，只不过时间恐怕就不是 O(1) 了罢了。
首先我们回忆一下一维 0-1 背包算法是怎么写的？
在这里就不分析这个算法了，不知道 0-1 背包算法的，呃……算导里竟然没有……那就自己 Google 好了……
先贴一个随手写的伪代码：
1 2 3 4 | for i = 1 to n
for j = size - s[i] to 0
if b[j] + v[i] > b[j+s[i]]
b[j+s[i]] = b[j] + v[i] |
唉……要是 Erlang 能像这个伪码这么简单就好了……
不过考虑到 Erlang 的特性，最后没有使用伪码这种形式，主要的改动有两点，一是把连续的大小数组改成了可能达大的大小的列表，二是使用双列表最后归并。至于记录路径什么的，都是小事……
最后贴代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | -module(knapsack). -export([calc/2]). calc(Objs, Size) -> K = [{0, 0, []}], calc(Objs, K, Size). calc([], K, _) -> final(K); calc([Obj|Objs], K, Size) -> NewK = calc(Obj, K, Size, []), FinalK = merge(lists:reverse(K), NewK), calc(Objs, FinalK, Size). final(K) -> lists:reverse(final(K, {0, []})). final([], {_, NameList}) -> NameList; final([{_, Val, List}|K], {MaxVal, _} = Cur) -> if Val > MaxVal -> final(K, {Val, List}); true -> final(K, Cur) end. calc(_, [], _, NewK) -> NewK; calc({_, ObjSize, _}, [{CurSize, _, _}|_], Size, NewK) when CurSize + ObjSize > Size -> calc(nothing, [], 0, NewK); calc({ObjName, ObjSize, ObjVal} = Obj, [{CurSize, CurVal, CurList}|K], Size, NewK) -> calc(Obj, K, Size, [{CurSize + ObjSize, CurVal + ObjVal, [ObjName|CurList]}|NewK]). merge(A, B) -> merge(A, B, []). merge([], [], K) -> K; merge(A, [], K) -> lists:reverse(A, K); merge([], B, K) -> lists:reverse(B, K); merge([{SizeA, ValA, ListA} = TA|LeftA] = A, [{SizeB, ValB, ListB} = TB|LeftB] = B, K) -> if SizeA > SizeB -> merge(LeftA, B, [TA|K]); SizeA < SizeB -> merge(A, LeftB, [TB|K]); ValA > ValB -> merge(LeftA, LeftB, [TA|K]); ValA < ValB -> merge(LeftA, LeftB, [TB|K]); length(ListA) < length(ListB) -> merge(LeftA, LeftB, [TA|K]); true -> merge(LeftA, LeftB, [TB|K]) end. |
用法解释：执行 knapsack:calc(物件列表, 背包大小)，其中物件列表中每个物件以元组 {物件名称, 物件大小, 物件价值} 表示，最终返回物件名称的列表，价值相同情况下这个算法会返回包内物件平均价值最高的一种选法 (数量最少)。此外，这个算法保证输出列表中物件的顺序与输入顺序相同。
我知道代码风格很丑……而且还没有精心调试过……因为终于写出来太高兴了，所以就马上贴了，如果各位觉得不太对，请及时指出！谢谢……
Comments