4.1 Algorithm 1- traditional 0-1 Knapsack Algorithm

Input

W_item : Weight of each item ,P_item: Profit of each item, C : Capacity

Output

SP : array of subproblem to find an optimal solution, X : 0 or 1 select item or not

Step 1

SP_ij ← {0, 0} // item : number of item , TN :total number of item

Step 2

for item = 1 to TN do // Capcount: : Capacity count

For Capcount ← 0 to C do

If W_item ≤ C then // SP : subproblem

If P_item + SPD[item -1, Capcount - W_item] > SP [item-1, Capcount] then

SPD[item -1, Capcount] ← P_item + SP[i - 1, j - W_item]

Else

SP [item , Capcount] ← SP [item -1, Capcount] // W_item > C

Endif

End for // Capcount

End for // item

Step 3

item← TN, Capcount ← C

Step 4

while item and Capcount > 0

If SP [item - 1 , Capcount] ≠ SP [item , Capcount] then

item ← item-1, Capcount ← Capcount- W_item

X_tem = 1

else

item ← item-1

X_tem = 0

end if

Endwhile