Standard Recursion Formula of 0/1 Knapsack

发表于   |   分类于   |  

Formula

DP[i][j] = f ( DP[i-1][j] , DP[i-1][j-weight[i]]+values[i] )
For this case, f is the max function.

Variables：

int n：number of cases
int N：number of items
int V：max volume of the knapsack
array values：value of each item
array weight：weight of each item

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//Title：0/1 Knapsack
//Author：Call偶围城
#include <stdio.h>
#define MAX 1005
int main() {
	int n;
	int N;
	int V;
	int values[MAX];
	int weight[MAX];
	int dp[MAX][MAX];
	int i,j;
	int t1,t2;
	scanf("%d", &n);
	while (n--) {
		scanf("%d%d", &N, &V);
		for (i = 1;i <= N;i++)
			scanf("%d", &values[i]);
		for (i = 1;i <= N;i++) 
			scanf("%d", &weight[i]);
		for (j = 0;j < MAX;j++) {
			dp[0][j] = 0;
		}
		for (i = 1;i <= N;i++) {
			for (j = 0;j <= V;j++) {
				if (weight[i] > j) {
					dp[i][j] = dp[i-1][j];
				}
				else {
					t1 = dp[i-1][j];
					t2 = dp[i-1][j-weight[i]] + values[i];
					if (t1 > t2)
						dp[i][j] = t1;
					else 
						dp[i][j] = t2;
				}
			}
		}
		printf("%d\n",dp[N][V]);
	}
	return 0;
}

Sample

Input
2
5 10
1 2 3 4 5
5 4 3 2 1
Output
14
the array dp
这里写图片描述

While weight often can be zero.
5 0
2 4 1 5 1
0 0 1 0 0

the result is 12.