### What is meant by “knapsack problem” and what is meant by 0-1 planning (linear programming class)

Knapsack problem: Have n items with weights w1,w2…wn and values c1,c2,…. .wn, value c1,c2,… ,cn, the maximum weight that the backpack can carry is W. Ask how to carry it to maximize the value.

List: maxz=cx,where c=(c1,c2,…. ,cn),x=(x1,x2… ,xn)T

s.t.w1*x1+w2*x2+… +wn*xn<=W

Where x1,… ,xn are 0-1 variables. (Carrying item i takes xi to be 1, otherwise it takes zero)

0-1 planning is a linear programming problem in which the unknown quantities take on only the values 0 or 1. The backpack problem is the 0-1 linear programming problem.

### 0/1 Backpacking Problem – Comparison of Dynamic Programming, Backtracking, and Branch-and-Limit Methods

Assume that the weights of the n commodities are w0,w1, … ,wn-1, and the values are p0,p1,… ,pn-1, and a backpack load of M. How can the combination of goods be chosen so as to maximize the value?

Maximum value estimation method (essentially the same as the branch-and-bound method)

Upward backtracking method

w_cur – denotes the total weight transferred in the part of the solution that is currently being searched for

p_cur. -the current total value

p_est-an estimate of the maximum possible value of the partial solution

p_total-the maximum value of all feasible solutions currently being searched for. is the upper bound of the current objective function

yk, xk – the kth component of the partial solution and its copy

k – denotes the current depth of the search

M=50

Commodity weights are 5, 15,25,27,30

Commodity values are 12,30,44,46,50

The above have been listed in decreasing order of value per unit weight.

Each node contains the following information:

S1 – the set of goods currently selected for the backpack

S2 – the set of goods not currently selected for the backpack

S3 — the set of goods currently remaining to be selected

k — the depth of the search

b — the upper bound

bound — The value of a feasible solution, when used as a criterion for pruning

Input description:

Output description:

Input examples:

Output examples:

### 0-1 backpack problem introductory detailed

On the Internet a lot of explanations about the backpack problem, they also read, feel that the explanation is not easy to understand, so they come to write a very easy to understand.

0-1 backpack problem says, given the backpack capacity W, a series of items {weiht,value}, each item can only take a piece, get the maximum value.

Solved using dynamic programming, the general rule of dynamic programming are,

In what what the previous i state of the maximum or minimum value of the premise, and then the value of the state of i to find out.

Here we define a function that represents the state.

m(1,2,3,4..i)(w) means that there are items #1,2,3,4…. .i)(w) is the maximum value that can be obtained when there are items #1, #2, #3, #4…i and the backpack capacity is w. For example,

Suppose items 1,2,3,4,5, whose weights are 2,2,6,5,4 respectively, are denoted by weight(i), and whose values are 6,3,5,4,6 respectively, are denoted by value(i)

m(1)(1) is the maximum value of the backpack when there is only item No.1 and the backpack capacity is 1. when the maximum value is reached. Obviously,

m(1)(1)=0, because the backpack capacity is less than 2, so the maximum value is 0.

m(1)(2)=6,at this time, the backpack capacity is equal to 2, and loaded with the item No.1, the maximum value is 6.Next

m(1)(3)=6,m(1)(4)=6. … . m(1)(…) = 6, since there is only one item, the maximum is 6.

m(1,2)(1),m(1,2)(2),m(1,2)(3) means the maximum value when there are items 1, 2, and the backpack capacity is 1,2,3 respectively.

The maximum value is related to the number of items, and also to the backpack capacity.

It must be emphasized here that m(1,2,3,…. .i)(w) means that there are 1,2,3,4… .i, so many items to choose from, and may not all fit (limited by w) the maximum value.

The next discussion is on the maximum value in the case of 1,2,3 …. Maximum value for .i item. For the ith item, the capacity of the backpack is W. There are two cases,

1) Do not load the ith item into the backpack, then at this point, there are only 1,2,3,4 ,,,,i-1 items, and the maximum value of the backpack is m(1,2,3,4,5…. .i-1)(W). At this point, no matter how big W is, even if it is as big as the universe, the sum of the values in the backpack is related to the items 1,2,3,4,5…i-1.

2) Putting the i-th item in. Since loading the i item into the backpack, the 1,2,3,4 …. .i-1 items can only take up so much weight as W-weight(i). At this point,

The previous 1,2,3,4….. .i-1 item has a maximum value of m(1,2,3 …… under a backpack capacity of (W-weight(i)) .i-1)[W-weight(i)].

The maximum value of the pack at this point is the value of the ith item value(i) plus

The first 1,2,3,4…. .i-1 items in the backpack capacity of (W-weight(i) under the maximum value m(1,2,3 …… .i-1)[W-weight(i)]

m(1,2,3,4…… .i-1,i)(W)=m(1,2,3…… .i-1)[W-weight(i)]+ value(i);

Then we compare, the maximum value of case 1) 2) is enough i.e.

m(1,2,3,4… .i-1,i)(W)=max[ m(1,2,3…… .i-1)[W-weight(i)]+ value(i), m(1,2,3,4,5… .i-1)(W)].

Some people here will say that the first 1,2,3,4 …. .i-1 items in W-weight or W capacity how to find it.

Here comes the point of dynamic programming. Dynamic programming is a little bit of mathematical induction, but from backward to forward, to solve for i, first solve for i-1,; to solve for i-1, first solve for i-2, and so on step by step up to 2,1. So you need to be given an initial state. We have been using 1,2,3,4 …. .i-1 to denote the first i-1 items, it’s too cumbersome, just use i-1.

m(1,2,3,4… .i-1)(w)====(easy to write)>m(i-1)(w), so that the state transfer equation above comes out.

m(i)(W)=max(m(i-1)(W-weight(i))+value(i),m(i-1)(w))

This way, the transfer of state equation comes out. Here I have to say, the other tutorials on the Internet on this point is not careful enough, up to get a

f[i-1][j]=max(f[i-1][j-w(i)]+value[i],f[i-1][j]). Who’s reading this.

Here we give the exact solution procedure for the values above. First give the function value of the item.

weight(1)=2,value(1)= 6,

weight(2)=2,value(2)=3,

weight(3)=6,value(3)=5,

weight(4)=5,value(4)=4,

weight(5)=4,value(5)= 6,

Then the maximum value function

m(1)(1)=0; the item weight is 2.

m(1) (2)=6,the item fits exactly in the backpack.

m(1)(3)=6, m(1)(4)=6… , there is only item #1 and the maximum value can only be 6. Now consider the case where there is a 2nd item, now there are two items and the m function is expressed as

m(1,2)(w).

According to what was said before 1), if item #2 is not put in, then the problem goes back to the case where there is only item #1

Then

m(1)(1)=0,item #1 does not go in,

m(1)(2)=6,item #1 goes in the backpack.

m(1)(3)=6,item #1 goes in the backpack with capacity 3

m(1)(4)=6,item #1 goes in the backpack with capacity 4.

According to what was said before 2), put item #2 into it, at this point you need item #1 in the backpack capacity w minus item #2’s capacity weight(2),i.e. the w-2 problem.

m(1)(1-2)=0, obviously, at this time, the total capacity of the backpack 1, there is subtracted from the capacity of the No. 2 item 2, 1-2=-1, obviously can not be put in.

m(1)(2-2)=0,Obviously, the capacity of the backpack minus the capacity of item 2, there is no remaining, that is to say, can only be put in item 2, at this time the maximum value of the backpack

m(1,2)(2) = max(m(1,2)(2-2)+value(2), m(1)(2))=max (0+3,6)=6. That is, in the case of 1,2 items and a pack capacity of 2, the maximum is 6.

Continuing to consider a pack capacity of 3, the first case has already been discussed. Now discuss the second case, putting item #2 into the backpack is going to leave w-2 capacity for #1.

m(1,2)(w-2)=m(1,2)(3-2)=m(1,2)(1) =0,value(2)=3 therefore,

m(1,2)(3)=max[ m(1,2)(3-2)+value(2),m(1)(3)] =max(0+3,6 )=6.

Continuing to consider a backpack capacity of 4, ditto for the first case discussed, and only for the second case, putting item 2 into the backpack is going to leave a capacity of w-2 for 1.

m(1,2)(4-2)=m(1,2)(2)=6,value(2)=3

m(1,2)(4)=max[m(1,2)(4-2)+value(2),m(1)(4)]=max[m(1,2)(2)+value(2),m (1)(4)]=max(6+3,6)=9;

At this point, m(1,2)(4)=9; after that, the backpack capacity is 5,6,7,. When 1,2 items are put in, the maximum value is no longer changed, they are all 9

m(1,2)(5)=9, m(1,2)(6)=9, m(1,2)(7)=9, m(1,2)(8)=9

similarly, weight(3)=6,value(3)=5

< p>

m(1,2,3)(1)=max[m(1,2,3)(1-6)+value(3),m(1,2)(1) ]=0

m(1,2,3)(2)=max[m(1,2,3)(2-6)+value(3),m(1,2)(2) ]=6

< p>

m(1,2,3)(3)=max[m(1,2,3)(3-6)+value(3),m(1,2)(3) ]=6

m(1,2,3)(4)=max[m(1,2,3)(4-6)+value(3),m(1,2)(4) ]=9

< p>

m(1,2,3)(5)=max[m(1,2,3)(5-6)+value(3),m(1,2)(5) ]=9

m(1,2,3)(6)=max[m(1,2,3)(6-6)+value(3),m(1,2)(6) ]=9

< p>

m(1,2,3)(7)=max[m(1,2,3)(7-6)+value(3),m(1,2)(7) ]=max[m(1,2,3)(1)+5,9]=max[0+5,9]=9

m(1,2,3)(8)=max[m(1,2,3) (8-6)+value(3),m(1,2)(8) ]=max[m(1,2,3)(2)+5,9]=max[6+5,9]=11;

The rest of the derivation is the same, just one step at a time, depending on the capacity of the pack.