Problem description

Given n items and a backpack, the weight of item I is wi, the value is VI, and the backpack capacity is C, how to choose items to be loaded into the backpack to maximize the total value of the items in the backpack? For each item, you can always choose to load it completely or not. An item can be loaded at most once.

Define the cost matrix M and the equation of state

m[i][j]

  • I: indicates the item ID. The value ranges from 0 to N-1. The value indicates that items from I to N-1 can be selected
  • J: Available backpack capacity
  • M [I][J] : When the available capacity of knapsack is J, the optimal cost of the problem is m[I][J].

Equation of state

Start with the item numbered N-1 until the initial number is 0

M [n-1][J] = 0, 0 ≤ j <w[n-1]

M [n-1][J] = V [n], j ≥ W [n-1]

M [I][j] = m[I +1][J], 0≤ j< w[I]

M [I] [j] = Max {m + 1] [I [j], m + 1] [I [j w. [I]] + v [I]}, j p w [I]

M [I] [j] = Max {m + 1] [I [j], m + 1] [I [j w. [I]] + v [I]} : the current items not into, with m + 1] [I [j] case, backpack capacity; Determine the current item into the backpack, new capacity = original capacity – current item weight, current value += current item value

For example,

Ex. : ,1,5 n = 3, w = {4}, v = w, C = 9 m (3, 9) = = 4 m (3, 8 ~ 4) m (3, 3 ~ 0) = 0 m (2, 9) = Max (m (3, 9), m (3, 8) + 1) = 5 m (2, 4) = Max (m (3, 4), m (3, 3) + 1) = 4 M (1, 9) = Max (m (2, 9), m (2, 4) + 5 = 9

code

public class KnapsackProb {

	/ * * *@paramArgs * Output: Line 1: maximum value; Line 2: Item number (starting from 0) */
	public static void main(String[] args) {
		int n=5,C=10;// Total number of items and total capacity
		int[] w= {2.2.6.4.5};/ / weight
		int[] v= {6.3.5.4.6};/ / value
// int n=3,C=9;
/ / int [] w = {1, four, five}; int[] v=w;
		int[][] m=new int[n][C+1];
		//m
		// the NTH item
		for(int j=0; j<=C; j++) {if(j<w[n-1])
				m[n-1][j]=0;
			else m[n-1][j]=v[n-1];
		}
		// Start item count from n-2 to 0
		for(int i=n-2; i>=0; i--) {for(int j=0; j<=C; j++) {if(j<w[i])/ / not put
					m[i][j]=m[i+1][j];
				else m[i][j]=Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);// It can be put down
			}
		}
		System.out.println(m[0][C]);// Maximum value
		M [I][j]>m[I +1][j]
		int j=C;
		// Check 0~n-2 items
		for(int i=0; i<n-1; i++) {if(m[i][j]>m[i+1][j]) {
				System.out.print(i+""); j=j-w[i]; }}if(m[n-1][j]! =0)
			System.out.print(n-1); }}Copy the code