DFS 在0-1背包问题中的使用

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
//DFS在0-1背包问题中的使用
#include <cstdio.h>
const int maxn = 30;
int n , V , maxValue = 0; //物品件数n,背包容量V , 最大价值maxValue
int w[maxn] , c[maxn]; //w[i]为每件物品的重量,c[i]为每件物品的价值
//dfs index为当前处理的物品编号
//sumW和sumC分别为当前的总重量和当前的总价值
void DFS(int index , in sumW , int sumC)
{
//临界条件
if(index == n+1)//已经完成对n件物品的选择
{
if(sumW <= V && sumC > maxValue)
{
maxValue = sumC; // 不超过背包容量时更新最大值maxValue
}
return ;
}
DFS(index+1 , sumW , sumC); //不选第index件物品
DFS(index +1 , sumW + w[index] , sumC + c[index]);//选第index件物品
}
int main()
{
scanf("%d%d" , &n , &V);
for(int i = 1 ; i <= n ; ++i)
{
scanf("%d" , %w[i]);
}
for(int i = 0 ; i <= n ; ++i)
{
scanf("%d" , &c[i]);
}
DFS(1 ,0 , 0);
printf("%d\n" , maxValue);
return 0;
}

热评文章