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
|
#define MAX 1005 int () { 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("%dn",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.
近期评论