问题描述：
设n个物品的编号为0~n-1，重量和价值分别用数组w【】与v【】存放，背包限制重量用W表示，X【】存放最优解，x【i】的值为0、1分别表示物品i不在、在背包内。
求解：
物品选择实际上就是一棵完全二叉树，左孩子对应选择当前物品，右孩子对应不选择。父节点的值对应当前选择下总的重量以及物品值，如图。
树的深搜其实就是先序、中序或者后续当中的一种，而回溯则是在此基础上，在某条函数自我调用语句的后面加上与上一步相反操作的语句，具体来看代码。
代码：
i代表当前物品编号，n代表物品总数，W代表背包限制重量，w【】和v【】分别存储对应标号物品的重量与价值，tw和tv代表当前节点的重量与价值，temp【】用来存储当前选择完成后的结果，x【】用来存放最优解，maxv作为选择最优解的指标。
复制代码
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#include<stdio.h> #include<iostream> using namespace std; #define max 10 void dfs(int i, int n, int W, int* w, int* v, int tw, int tv, int* temp, int* x, int maxv) { if (i == n) { if (tw == W && tv > maxv) { maxv = tv; for (int j = 0; j < n; j++) x[j] = temp[j]; } return; } temp[i] = 1; dfs(i + 1, n, W, w, v, tw + w[i], tv + v[i], temp, x, maxv); temp[i] = 0; dfs(i + 1, n, W, w, v, tw, tv, temp, x, maxv); } int main() { int w[] = { 5,3,2,1 }; int v[] = { 4,4,3,1 }; int x[max]; int temp[max]; memset(x, 0, sizeof(x)); memset(temp, 0, sizeof(temp)); int n = 4; int W = 6; int maxv = 0; dfs(0, n, W, w, v, 0, 0, temp, x, maxv); for (int i = 0; i < n; i++) cout << x[i] << " "; return 0; }
可以看到，其实回溯关键的语句就一句：
复制代码
1temp[i] = 0;
如果去掉这一句，就是标准的树的先序遍历。
复制代码
1
2
3temp[i] = 1; dfs(i + 1, n, W, w, v, tw + w[i], tv + v[i], temp, x, maxv); dfs(i + 1, n, W, w, v, tw, tv, temp, x, maxv);
最后
以上就是斯文绿茶最近收集整理的关于回溯法经典例题--0/1背包问题--C语言的全部内容，更多相关回溯法经典例题--0/1背包问题--C语言内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复