header

MultipleKnapsack : Solving the so- called multiple knapsack problem.
Tag:
Edit edit   Starstar

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