Java knapsack problem solving example code

Knapsack problem mainly refers to a given capacity knapsack and several items with certain value and weight. How to select items to put into the knapsack to maximize the value of items. It is also divided into 01 backpack and infinite backpack. Here we mainly discuss 01 backpack, that is, each item can be placed at most. The infinite backpack can be transformed into 01 backpack.

Let's talk about the main idea of the algorithm and solve it by dynamic programming. For the i-th item traversed each time, determine whether to put the item into the backpack according to w [i] and v [i]. That is, for a given n items, let v [i] and w [i] be the value and weight of the ith item respectively, and C be the capacity of the backpack. Let v [i] [J] represent the maximum value that can be loaded into the backpack with capacity J in the first I items. Then we have the following results:

(1) , v [i] [0] = v [0] [J] = 0; (2), v [i] [J] = v [I-1] [J] when w [i] > J (3), v [i] [J] = max{v [I-1] [J], v [I-1] [J-W [i]] + v [i]} when J > = w [i]

OK, our algorithm is based on these three conclusions.

1、 01 backpack:

1. Two dimensional array method

Output:

The time and space complexity of the above methods are o (n * V). The time complexity can no longer be optimized, but the space complexity can be optimized to o (V).

First consider how to realize the basic idea mentioned above. There must be a main loop I = 1 N. Calculate all the values of the two-dimensional array f [i] [0.. v] each time. Then, if only one array f [0.. v] is used, can we ensure that the state f [i] [v] defined by us is represented in F [v] after the end of the i-th cycle? F [i] [v] is derived from the two subproblems f [I-1] [v] and f [I-1] [V-C [i]]. Can we ensure that the values of F [I-1] [v] and f [I-1] [V-C [i]] can be obtained when pushing f [I] [v] (that is, when pushing f [v] in the ith main cycle)? In fact, this requires us to push f [v] in the order of V = v.. 0 in each main cycle, so as to ensure that f [V-C [i]] saves the value of state f [I-1] [V-C [i].

The pseudo code is as follows:

The sentence f [v] = max{f [v], f [V-C [i]]} is exactly equivalent to our transfer equation f [i] [v] = max{f [I-1] [v], f [I-1] [V-C [i]]}, because the current f [V-C [I]] is equivalent to the original f [I-1] [V-C [i]]. If the cyclic order of V is changed from the above reverse order to the order, then f [i] [v] is inferred from F [i] [V-C [i]], which is inconsistent with the meaning of this problem, but it is the simplest solution to another important knapsack problem P02. Therefore, it is necessary to learn to solve the 01 knapsack problem with only one dimension group.

In fact, there are two different ways to solve the knapsack problem for the optimal solution. Some problems require the optimal solution when "just fill the backpack", while others do not require that the backpack must be filled. One difference between the two methods is that they are implemented differently during initialization.

If the first method requires that the knapsack be exactly filled, f [1.. v] is set to - ∞ except that f [0] is 0 during initialization, so as to ensure that the final f [n] is an optimal solution just filled with the knapsack.

If it is not required to fill the backpack, but only want the price to be as large as possible, f [0.. v] should be set to 0 during initialization.

Why? It can be understood that the initialized f array is actually the legal state when there are no items to put into the backpack. If the backpack is required to be exactly full, only the backpack with capacity 0 may be "exactly full" by nothing with value 0. The backpacks with other capacity have no legal solution and belong to an undefined state, so their values should be - ∞. If the backpack does not have to be filled, then the backpack of any capacity has a legal solution "nothing", and the value of this solution is 0, so all the values of the initial state are 0.

2. One dimension group method (without filling)

output

3. One dimension group method (must be full)

output

2、 Complete Backpack

There are n items and a backpack with a capacity of V. there are unlimited items available for each item. The cost of item I is C [i], and the value is w [i]. Solve which items are loaded into the backpack, so that the total cost of these items does not exceed the backpack capacity, and the total value is the largest.

But we have a better o (VN) algorithm.

O (VN) algorithm

This algorithm uses a one-dimensional array. First look at the pseudo code:

You will find that this pseudo code is different from the pseudo code of P01 only in the cyclic order of V.

output

summary

The above is all about the Java knapsack problem solving example code in this paper. I hope it will be helpful to you. Interested friends can continue to refer to this site: detailed examples of Java Monte Carlo algorithm for calculating the approximate value of PI, examples of Java applet for calculating the circumference and area of a circle Java programming uses the stack to find code examples (non recursive) to solve the Hanoi Tower problem. If there are deficiencies, you are welcome to leave a message and point out that the Xiaobian will reply to you in time and make modifications, and strive to provide the majority of programming work and enthusiasts with better articles and better reading experience. Thank you for your support to this site!