0-1-Knapsack Profit-Maximisation Problem

Definition

0-1-Knapsack Profit-Maximisation Problem

The 0-1-Knapsack profit-maximisation problem is the optimisation form of the 0-1-Knapsack problem.

Instance: a 0-1-Knapsack instance

$$I=((w_1,p_1),\dots ,(w_n,p_n),W).$$

Feasible solutions:

$$F(I)=\left\{x\in \{0,1{\}}^n|\sum _{i=1}^n{w}_i{x}_i\le W\right\}.$$

Objective: find $x^{\star }\in F(I)$ satisfying

$$x^{\star }\in \underset{x\in F(I)}{\mathrm{argmax}}\sum _{i=1}^n{p}_i{x}_i.$$

Its optimal value is

$$\mathrm{OPT}(I)=\underset{x\in F(I)}{\max }\sum _{i=1}^n{p}_i{x}_i.$$