0-1 knapsack problem (DP)

Problem Description:

Given n items and a backpack, the weight of item i is Wi and its value is Vi, design a dynamic programming algorithm to select the items to be loaded into the backpack such that the total value of the items loaded into the backpack is maximized. In selecting the items to be loaded into the backpack, there are only two choices for each item i, i.e., to load it into the backpack or not to load it into the backpack. Items i cannot be loaded into the backpack more than once, nor can only a portion of item i be loaded. The requirements are as follows:
(1) Input: Requires that the number of items, the weight and corresponding value of the items, and the total capacity of the backpack can be entered by the user.
(2) Output: the total value of the backpack, and which items went into it.

Algorithmic thinking

First, the 0-1 problem has an optimal substructure, i.e., let (y1,y2,...,yn)yi∈ {0,1} (0 means no choice, 1 means choice) is an optimal solution to the 0-1 knapsack problem, then (y2,y3,...,yn) is the subproblem

An optimal solution for the
Let m(i, j) be the optimal value of the 0-1 knapsack problem when the knapsack capacity is j and the selectable items are the i, i+1, ..., nth items, e.g., m(3,10), means that, with a knapsack capacity of 10, the items that can be selected are the 3rd to the nth items, which maximizes the value of the selected items. So, m(1,j) is the solution of the backpack problem.

Analysis:

1. If the weight of the ith item is greater than the capacity of the backpack, then the ith item is not loaded into the backpack, i.e.

        m(i，j)=m(i+1,j)

2. If the weight of the ith item is less than the capacity of the backpack, the following two cases will occur:
(a) If the ith item is loaded into the backpack, the value of the item in the backpack = m(i+1,j-w[i]) + v[i]
(b) If the ith item is not loaded into the backpack, the value of the item in the backpack = m(i+1,j)
Take the largest value of the two as the optimal solution.

     max(m(i+1,j), m(i+1,j-w[i])+v[i])

Boundary conditions:

When j=0, i.e., the backpack capacity is 0, then m(i,j)=0;
When i=n, i.e., only the nth item can be selected, if w[i] <= j , i.e., the backpack can hold the nth most item, then m(i,j)=v[n], otherwise, m(i,j)=0;

In summary.

Dynamic programming algorithm solution process.

Initial: m[i][0]=0,i=1,2,......,n
Calculate m[n,j],j=1,2,......,c (c is backpack capacity)
Step 1: Calculate m[n-1,j], j=1,2, ......,c
Step 2: Calculate m[n-2,j], j=1,2, ......,c
......
Step i: Calculate m[n-i,j], j=1,2, ......,c
......
Step n-2: Calculate m[2,j], j=1,2 ......,c
Step n-1: Calculate m[1,j], j=1,2, ......,c

Specific algorithms:

#include""
#include""
#include""
int max(int x,int y){
	int retValue = x>y?x:y;
	return retValue;
}
void knapsack(int n,int c,int *w,int *v,int **m){
	int i,j;
	// When the weight of the backpack is 0, c[i][0]=0;
	for(i=0;i<=n;i++)
		m[i][0]=0; 
	// Boundary condition: the value of m when there is only the nth object and the capacity of the backpack is 1,2,...,c, respectively
	for(j=1;j<=c;j++)
	    if(j>=w[n])
	    	m[n][j]=v[n];
	    else 
			m[n][j]=0;
	//Solve m[i][j] in turn,1<=i<n,1<=j<=c
	for(i=n-1;i>=1;i--) 
		for(j=1;j<=c;j++)
			if(j<w[i])
				m[i][j]=m[i+1][j];
			else
				m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
	printf("MaxValue=%d\n",m[1][c]);
}

//Specific items selected
void traceback(int **m ,int *w, int c, int n, int *x){
	//find x[i], starting from m[1][c]
	int j=c,i;
	for(i=1;i<n;i++){
	    if(m[i][j]==m[i+1][j])//No items added
	        x[i]=0;
	    else{
	        x[i]=1;
	    	j=j-w[i];
		}
	}
	if (m[i][j]>0)
	   	x[n]=1;
	else               
	   	x[n]=0;
}
int main(){
	int n;//nums of goods 
	int c;//capacity
	scanf("%d%d",&n,&c);
	int *w=(int*)malloc(sizeof(int)*(n+1));//weights
	int *v=(int*)malloc(sizeof(int)*(c+1));//values
	int *x=(int*)malloc(sizeof(int)*(n+1));//goods chosed
	int i;
	for(i=1;i<=n;i++)
		scanf("%d",&w[i]);//start with index 1
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);//start with index 1
	w[0]=0;v[0]=0;
	int **m=(int**)malloc(sizeof(int*)*(n+1));//m[i][j] means j capacity with i...n goods to choose
	for(int i=0;i<n+1;i++){
		m[i]=(int*)malloc(sizeof(int)*(c+1));
	}
	knapsack(n,c,w,v,m);
	traceback(m,w,c,n,x);
	printf("goods chosed:");
	for(i=1;i<=n;i++)
		if(x[i]==1)
			printf("%d ",i); 
}

Test data:

(1) There are 7 items, w={2,3,5,7,1,4,1}, v={10,5,15,7,6,18,3}, and the capacity of the backpack c is 15.
(2) There are 5 items, w={2,2,6,5,4}, v={6,3,5,4,6}, and the capacity of the backpack c is 10.