Thinking: The number of sub-problems to be solved is not only changed, but also the conditions of judgment will change. We choose to remember both the sub-problems and the changing conditions, and save the optimal results of all the sub-problems under the changing conditions as the solution of the parent problem

Knapsack problem

There are n objects, each of which has a weight of zeroIs an Integer, and each object has a value of, the backpack can hold the weight of S, each time to obtain the maximum value of the loading method.

The analysis is as follows: The weight that the backpack can hold is limited, if the weight of the object itself is greater than the backpack can hold the range, no matter how large the value can not be loaded, for the remaining weight is less than the backpack can hold the range:

• Suppose you choose to install object A, then the value is, remaining weight $S-S_a
• If you choose not to load object A, then you can select one of the remaining objects that can be loaded

There are two kinds of schemes to choose, which way makes the maximum value on the corresponding installation way

• X is the current capacity of the backpack
• I-1 represents the current contents of the backpack
• Represents the current object weight
• DP(i-1,X) indicates that no object is installed
• DP(i-1, x-s_i)+V_i represents the value of the current installed capacity
• DP(i-1,X-S_i) represents the value of the maximum capacity under the remaining weight

Assume the following example:

There are three items in total and the backpack is limited to 5kg. Item A is worth 10 yuan, 4kg B is worth 4 yuan, 2kg C is worth 7 yuan, 3kgCopy the code

You start with nothing in the backpack, so you start with nothing, and the value in the backpack is 0.

The horizontal axis represents the weight that the backpack can hold, the vertical axis represents the object, and each cell represents the maximum value that the backpack can hold in the corresponding weight

Assume that there is only one object A at this time, and its weight is 4kg. According to the condition that the backpack can be loaded, the capacity of the backpack must be at least 4kg. Otherwise, no matter how much the value is, the capacity is not enough

The value 0 indicates that the capacity is 0

At this point, capacity has reached 4, and you have two choices

• If you don’t install A, the value is 0 and the remaining capacity is 5
• If you load A, you’re worth 10, you’re losing 4, you’re left with 0, and DP(0,0) is worth 0 if you have 1 and nothing to fill it with

You can see that the value of loading A is greater

DP(0,1)+10=0+10>DP(0,5)=0, so it is more valuable to continue loading A

The options for object A are exhausted, so ‘A is already in the backpack ‘. Consider object B, which weighs 2kg

• The backpack adds value only if it has the capacity to carry it
• When the capacity is 2, A is not fit, at this time the value of the original backpack is 0, loading can bring value
• When capacity is 3, you can still only hold B

Things change a little bit at capacity 4

• If B is not loaded, the backpack is already loaded with A, and the value DP(1,4)=10
• Loading B is worth 4, and the remaining capacity is 3, while at capacity 3, the initial value is DP(1,3)=0, and the total value is 4

It can be seen that when the capacity of A and B is 4, it is A better choice to install only A, and the same situation applies to capacity 5

And then we’re going to think about C, where we’ve already thought about carrying A and B in the backpack

• When the capacity is 0 and 1, the original backpack carries nothing, and the capacity is not up to the weight of C, right
• When the capacity is 2, C still cannot be loaded, but without C, the best value can be obtained from the results of A and B is DP(2,2)=4

When the capacity is 3

• Without C, original value is DP(2,3)=4
• Pack C, original value is 7+DP(2,0)=7

DP(2,0) means that in the case of 0 capacity, both A and B consider whether to install the optimal value

It’s better to just put C

When the capacity is 4

• The original value is DP(2,4)=10
• Load C, bring value 7, lose weight 3, remaining 1, total value DP(2,1)+7=7

It’s better not to have a C

When the capacity is 5

• DP(2,5)=10 without C
• Load C, bring value 7, lost weight 3, remaining weight 2, total value DP(2,2)+7=4+7=11

With better C

From this, it can be concluded that the capacity is 5 and the optimal value under the current condition is 11. The following code

public static void main (String[] args) throws Exception{
//code
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int round=Integer.parseInt(br.readLine());
for(int r=1; r<=round; R++){int N= integer.parseint (br.readline ()); Int W= integer.parseint (br.readline ()); String[] vStrs=br.readLine().split("");
            String[] wtStrs=br.readLine().split("");
            int[] v=new int[N+1];
            int[] wt=new int[N+1];
            for(int i=0; i<N; I ++){// Object value v[I]= integer.parseInt (vStrs[I]); // Weight of object wt[I]= integer.parseInt (wtStrs[I]); } int[][] dpV=new int[N+1][W+1];for(int i=1; i<=N; i++){for(int j=1; j<=W; j++){ int result=dpV[i-1][j];if(wt[i-1]<=j){ result=Math.max(v[i-1]+dpV[i-1][j-wt[i-1]],dpV[i-1][j]); } dpV[i][j]=result; } } System.out.println(dpV[N][W]); }}Copy the code

The total elapsed time is O(NW), depending on both the size of the backpack and the number of items.

Pseudo polynomial running time

The time required for the backpack problem is O(ns), where S represents the maximum capacity of the backpack, the maximum allowable size of an object is S, and the space needed to store logS on the computer is at least. The total number of numbers to be processed is N, so the cost of space is O(nlogS). Assuming logS=b, i.e. the input size is O(NB), then the running time isThat is, the running time increases exponentially as the input gets bigger, but if b is small, it’s polynomial running time, and that’s called pseudo-polynomial running time.