-
Notifications
You must be signed in to change notification settings - Fork 0
/
bag01.c
128 lines (117 loc) · 3.97 KB
/
bag01.c
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/* 01背包问题
设dp[i][v]表示 此时前i件物品放入一个容量还剩v的背包中可以获得最大价值
向前倒退一步
对于第i-1件物品，其表示可能有两种情况
1、当第i件物品没有放入时，则放入第i-1件物品之后背包剩余容量应该和放入第i件物品后的背包剩余容量相同
为v，所以为dp[i-1][v]，价值也应该是和dp[i][v]相等的。
2、当第i件物品放入时，则放入第i-1件物品之后背包剩余容量应该比放入第i件物品后的背包剩余容量多了c[i]
所以为dp[i-1][v-c[i]]，价值应该是比dp[i][v]少了第i件物品的价值
所以综上所述，dp[i][v]可以表示为dp[i-1][v] 和 dp[i-1][v-c[i]]+w[i] 其价值较大的那个
即 dp[i][v] = max(dp[i-1][v], dp[i-1][v-c[i]]+w[i]);
当v=0时，dp[i][0]结果肯定为0，因为背包容量为0的话，放不了任何东西，价值肯定为0
当i=0时，dp[0][v] = max(w[0],0)，为第0件物品的价值或0中的较大者
*/
/* 动态规划 */
#include<stdio.h>
#include<string.h>
#define N 1010
#define max(a,b) (a)>(b)?(a):(b)
int dp[N][N];
int n, m;
int w[N], c[N];
void bag01(){
int t;
scanf("%d", &t);
while (t--){
memset(dp, 0, sizeof(dp));
memset(w, 0, sizeof(w));
memset(c, 0, sizeof(c));
scanf("%d%d", &n, &m);
int i,j;
for (i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (i = 1; i <= n; i++){
for (j = 0; j <=m; j++){
if (j - c[i] >= 0)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
printf("dp数组内容为\n");
for(i=0; i<=n; i++){
for(j=0; j<=m; j++)
printf("%d ", dp[i][j]);
printf("\n");
}
printf("所选择的物品为:\n");
i = n;
j = m;
while(i>0 && j>0){
if(dp[i][j] == dp[i-1][j-c[i]]+w[i]){//dp数组中隐藏着路径信息
printf("%d ", i);
j -= c[i];
}
i--;
}
printf("\n最大价值为%d\n", dp[n][m]);
}
}
/*
观察dp[i][j] = max{dp[i-1][j], dp[i-1][j-c[i]]+w[i]}
第i行第j列只与i-1行第j列和i-1行v-c[i]列有关，
即本行只与上一行有关，所以可以只用一个一维数组保存第i-1行的各列值，到了i行之后，用原数组的相关值
来推i行的各列值，然后覆盖原数组，以达到节省空间的目的
状态转移方程变为: dp[j] = max(dp[j], dp[j-c[i]]+w[i])
要注意的是：此处的j要从后往前递减，因为dp[j]的值是和dp[j-c[i]]有关，而j-c[i]<j，也就是说
如果j从左往右递增的话，dp[j]的值由左边的值推出，dp[j+n]的值也会由左边的值推出，而此时左边的值已经
被dp[j]及其左边的值给覆盖了
*/
/*空间复杂度优化，将二维数组优化为一维数组*/
//void bag01(){
// int dp[N];
// int t;
// scanf("%d", &t);
// while (t--){
// memset(dp, 0, sizeof(dp));
// memset(w, 0, sizeof(w));
// memset(c, 0, sizeof(c));
// scanf("%d%d", &n, &m);
// int i,j;
// for (i = 1; i <= n; i++)
// scanf("%d", &w[i]);
// for (i = 1; i <= n; i++)
// scanf("%d", &c[i]);
//
// for (i = 1; i <= n; i++){
// for (j = m; j >= c[i]; j--){
// dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
// }
// }
// for(i=0; i<=m; i++)
// printf("%d ", dp[i]);
// printf("\n");
// printf("%d\n", dp[m]);
// }
//}
int main()
{
bag01();
return 0;
}
/*
1
6 10
5 6 5 1 19 7
2 3 1 4 6 5
0 0 0 0 0 0 0 0 0 0 0
0 0 5 5 5 5 5 5 5 5 5
0 0 5 6 6 11 11 11 11 11 11
0 5 5 10 11 11 16 16 16 16 16
0 5 5 10 11 11 16 16 16 16 17
0 5 5 10 11 11 19 24 24 29 30
0 5 5 10 11 11 19 24 24 29 30
*/