Max-Value Knapsack

computation

Definition

Max-Value Knapsack

Given items $a_1,a_2,\dots ,a_n$, where each $a_i$ has a positive integer value $\mathrm{val}(a_i)\in {\mathbb{Z}}^{+}$ and size $\mathrm{s}(a_i)\in {\mathbb{Z}}^{+}$, and a knapsack size $S$, find a subset of items whose size is bounded by $S$ and total value maximised.