http://www.nct9.ne.jp/m_hiroi/prolog/clp02.html
上記urlには、swi-prolog + clpfd による様々な制約プログラミングが、 分かりやすく記載されています。
その中に swi-prolog + clpfd による ナップザック問題もありますが、 流石 prolog という程、簡潔に記載されています。
他の言語では、ここまで簡潔にはなりませんよね。
use_module(library(clpfd)). solver :- Ws = [3, 4, 5, 7, 9], Ps = [4, 5, 6, 8, 10], Bs = [A, B, C, D, E], Bs ins 0..1, scalar_product(Ws, Bs, #=<, 15), scalar_product(Ps, Bs, #=, V), labeling([max(V)], [A, B, C, D, E, V]), writeln(V), writeln(Bs).
use_module(library(clpfd)). solver(W) :- % 単価 % A: 30.3, B: 30.0, C: 30.5, D: 31.0 Price = [91, 120, 610, 930], Size = [3, 4, 20, 30], Vars = [A, B, C, D], maplist(#=<(0), Vars), scalar_product(Size, Vars, #=<, W), scalar_product(Price, Vars, #=, Value), labeling([down, max(Value)], [D, C, A, B, Value]), writeln(Value), writeln(Vars).