The Knapsack Code is based on the Knapsack Problem given num

The Knapsack Code is based on the Knapsack Problem: \"given numbers a_1, a_2, ... a_n and a target value of t determine if there is a subset of a_1, a_2, ... a_n such that the sum of the numbers in the subset adds up to t.\" In more formal terms, we want to be able to write the following; x_1 a_1 + x_2 a_2 + + x_n a_n - 1 where all the x_1\'s are 0 or 1. Given a bag with weights 1, 5, 6, 11, 14, 20, can I select weights from the bag that add to 22? Can I get a sum of 24? Easy knapsack: If list of weights is a superincreasing sequence, the knapsack problem is easy. Superincreasing means every term is greater than the sum of all the easy previous terms. Which of (1, 3, 4, 9, 15, 25) and (1, 3, 6, 13.27, 52) is superincreasing? A solution to the superincreasing knapsack is easy to find. You simply find the largest weight than the sum that you want and place that in the knapsack. Then subtract that weight that is smaller the process with the remaining available weights. The problem is much harder without a superincreasing sequence. Consider the weights (2, 3, 6, 13, 27, 52) and total weight 70. Pack the using the method from the above paragraph. Suppose that we want a sum of 45 from A = (2, 3, 6, 13, 27, 52) following scheme: is the weight is in the knapsack we give that position a 1. If not, it gets a 0. So for 45 = 2 + 3 + 13 + 27 we give 2 3 6 13 27 52 45 rightarrow 1 1 0 1 1 0 is the binary code. Convert your knapsack from problem 3 to binary.

Solution

a) Yes

0*1 + 1*5 + 1*6 + 1*11 +0*14 + 0*20 = 22

No 24 sum cannot be derived from this bag

b) Sequence (1,3,4,9,15,25) is not superincreasing as it is failing at weight 15 (expected number should be greater than or equal to 17)

(1,3,6,13, 27,52) is superincreasing as it abides all rules

c)

Knacksack = {2} total weight = {68}

Knacksack = {2, 3} total weight = {65}

Knacksack = {2,3,6} total weight = {59}

Knacksack = {2,3,6,13} total weight = {46}

Knacksack = {2,3,6,13,27} total weight = {29}

Hence, final knacksack = {2,3,6,13,27}

d) Binary for knacksack = {2,3,6,13,27} is 111110