subseq([], []).
subseq([I|Is], [I|T]) :- subseq(Is, T).
subseq(Is, [_|T]) :- subseq(Is, T).

ntoulapi([food(bread,4,9200),
	  food(pasta,2,4800),
	  food(peanutButter,1,6700),
	  food(babyFood,3,6600)]).

k_decision(Items, Capacity, Goal, Knapsack) :-
    subseq(Knapsack, Items),
    weight(Knapsack, 0, Weight),
    Weight =< Capacity,
    calories(Knapsack, 0, Calories),
    Calories >= Goal.

weight([], W, W).
weight([food(_,W,_) | T], Win, Wout) :-
    Wmid is Win + W,
    weight(T, Wmid, Wout).

calories([], C, C).
calories([food(_,_,C) | T], Cin, Cout) :-
    Cmid is Cin + C,
    calories(T, Cmid, Cout).

k_legal(Items, Capacity, Knapsack) :-
    subseq(Knapsack, Items),
    weight(Knapsack, 0, Weight),
    Weight =< Capacity.

k_opt(Items, Capacity, Knapsack) :-
    findall(K, k_legal(Items, Capacity, K), KList),
    maxCalories(KList, Knapsack).

maxCalories([K|Ks], MaxK) :-
    calories(K, 0, Icals),
    maxC(Ks, K, Icals, MaxK).

maxC([], K, _, K).
maxC([K|Ks], _, MaxC, MaxK) :-
    calories(K, 0, Kcals),
    MaxC =< Kcals,
    maxC(Ks, K, Kcals, MaxK).
maxC([K|Ks], SoFarK, MaxC, MaxK) :-
    calories(K, 0, Kcals),
    MaxC > Kcals,
    maxC(Ks, SoFarK, MaxC, MaxK).