### Program Information

Name: MultipleKnapsack
Domain: Optimization algorithms
Functionality: Solving the so- called multiple knapsack problem.
Input:
$P(p_{1},p_{2},\cdots,p_n)$: The profit of items(Type: Set) $W(w_{1},w_{2},\cdots,w_n)$:The weight of items(Type: Set) $C(c_{1},c_{2},\cdots,c_m)$:The capacity of knapsacks(Type: Set)
Output:
T:The solution of the problem(Type: Integer) $Y(y_{1},y_{2},\cdots,y_n)$:An array of the solution(Type: Array)

#### Reference

How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46

### MR Information

#### MR1

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Changing the order of $P_s$ $W_f$ = Changing the order of $W_s$ $C_f = C_s$
Output relation: $T_f = T_s$

#### MR2

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = All profits of $P_s \times x$, where x is a positive integer. $W_f = W_s$ $C_f = C_s$
Output relation: $T_f = T_s \times x$ $Y_f = Y_s$

#### MR3

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = All profits of $P_s \times x$ $W_f$ = All weights of $W_s \times x$ $C_f$ = All capacities of $C_s \times x$, where x is a positive integer.
Output relation: $T_f = T_s \times x$ $Y_f = Y_s$

#### MR4

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f = P_s$ $W_f$ = All weights of $W_s \times x$ $C_f$ = All capacities of $C_s \times x$, where x is a positive integer.
Output relation: $T_f = T_s$ $Y_f = Y_s$

#### MR5

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Increasing or Decreasing profits of $P_s$ $W_f = W_s$ $C_f = C_s$
Output relation: $T_f > T_s$ or $T_f < T_s$

#### MR6

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f = P_s$ $W_f$ = Increasing or Decreasing weights of $W_s$ $C_f = C_s$
Output relation: $T_f \le T_s$ or $T_f \ge T_s$

#### MR7

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f = P_s$ $W_f = W_s$ $C_f$ = Increasing or Decreasing capacities of $C_s$
Output relation: $T_f \ge T_s$ or $T_f \le T_s$

#### MR8

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Decreasing profits of unselected items in $P_s$. $W_f = W_s$ $C_f = C_s$
Output relation: $T_f = T_s$ $Y_f = Y_s$

#### MR9

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Increasing profits of selected items in $P_s$. $W_f = W_s$ $C_f = C_s$
Output relation: $T_f > T_s$ $Y_f = Y_s$

#### MR10

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f = P_s$. $W_f$ = Increasing weights of unselected items in $W_s$ $C_f = C_s$
Output relation: $T_f = T_s$ $Y_f = Y_s$

#### MR11

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Swapping $p_{j1}$ and $p_{j2}$ of $P_s$. $W_f$ = Swapping $w_{j1}$ and $w_{j2}$ of $W_s$. $C_f = C_s$
Output relation: $T_f = T_s$ $Y_f$ = Swapping $y^s_{j1}$ and $y^s_{j2}$ of $Y_s$

#### MR12

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Increase the profit of a selected item to the highest profit in the selected items of $P_s$. $W_f = W_s$ $C_f = C_s$
Output relation: $T_f \ge T_s$

#### MR13

Source input: $P_s,W_s,C_s$ ; Source output: $T_s,Y_s$
Follow-up input: $P_f,W_f,C_f$ ; Follow-up output: $T_f,Y_f$
Input relation: $P_f$ = Increasing the smallest profit of $P_s$. $W_f = W_s$ $C_f = C_s$
Output relation: $T_f \ge T_s$

### Related

Insert title here