size[object_] := object[[1]]
value[object_]  := object[[2]]

total[knapsack_, vs_]  := Plus @@  value /@ vs[[knapsack]] (* total value *)
contents[knapsack_, vs_] := Plus @@ size /@ vs[[knapsack]] (* total size *)

KnapsackGraph[{}, s_Integer?NonNegative] :=
	{{}, {node[{s, 0}, 0]}}

KnapsackGraph[vs_List, s_Integer?NonNegative] :=
    Module[{sn = size[Last[vs]], n = Length[vs],
            rest = Drop[vs, -1], k1, k2, g, k, g1, g2},
        {k1, g1} = KnapsackGraph[rest, s];
        If[ s >= sn,
            {k2, g2} =  KnapsackGraph[vs, s - sn];
            k2 = Append[k2, n];
            If[ total[k1, vs] >= total[k2, vs],
                k = k1; g = {arrow[{s, n}, {s, n-1}, True],
                             arrow[{s, n}, {s - sn, n}]};
              , k = k2; g = {arrow[{s, n}, {s, n-1}],
                             arrow[{s, n}, {s - sn, n}, True]};
                        {g1,g2} = {g2,g1};
              ]
          ,
            k = k1; g = {arrow[{s, n}, {s, n-1}, True]};
            g2 = {};
          ];
        {k, Join[g, {{GrayLevel[0.2], g2}, g1, node[{s, n}, total[k, vs]]}]}
    ]

diskr = 0.42                            (* Disk Radius *)
sf = 2                                  (* vertical scaling *)
scale[{x_, y_}] := {x, sf y}
node[xy_List, text_] := {
 {GrayLevel[1], Disk[ scale[xy], diskr ]}, Circle[ scale[xy], diskr ], Text[ text, scale[xy] ]
}

t0 = 0.4; t1 = 1.1; (* Thickness[] in Points *)
arrow[from_, to_, bold_:False] :=
    {AbsoluteThickness[If[bold, t1, t0]], Line[{scale[from], scale[to]}]}

xticks[min_, max_] := Range[Round[min+1], Round[max-1], 2]
yticks[min_, max_] := Table[ {i, i/2}, {i, Round[sf(min+1)], Round[sf(max-1)], sf}]

KnapsackPlot[vs_List, s_Integer?NonNegative, opts___] :=
    Module[{gr},
        gr = KnapsackGraph[vs, s][[2]];
        Show[Graphics[gr], opts,
             Frame -> True, AspectRatio -> Automatic,
             FrameLabel -> {"s", "n"},
             PlotRange -> {{-1, s+1}, {-1, sf Length[vs]+1}},
             FrameTicks -> {xticks, yticks, xticks, yticks}]
    ]
