动态规划 / 回溯算法【01背包问题】（C语言）动态规划 01背包问题问题描述：回溯

107 阅读 0 评论 71 点赞

我是靠谱客的博主专注蜡烛，这篇文章主要介绍动态规划 / 回溯算法【01背包问题】（C语言）动态规划 01背包问题问题描述：回溯，现在分享给大家，希望可以做个参考。

动态规划 01背包问题

动态规划处理当前项时，只有两种选择：选 / 不选。
那么问题简化为：什么情况选，什么情况不选（出口）

在这里插入图片描述

问题描述：

现在有4个物品，背包总容量为8，物品如何装入背包总价最大

01背包问题：每种物品只能装一次

出口有 3 种：

$i f : 背包剩余可装重量为 0 ：不能装任何一个物品，此时总价 v a l u e = 0 （第一列初始值）$
$i f : 没有物品：背包也选不了物品，此时总价 v a l u e = 0 （第一行初始值）$
$i f : 物品重量大于背包剩余重量，只能不选$

复制代码

1
2
3
4
物品编号  1  2  3  4
物品体积  2  3  4  5
物品价值  3  4  5  6

复制代码

# include <stdio.h>
# include <stdlib.h>

int weight[5] = {0, 2, 3, 4, 5}; // 0 ：背包容量已用完
int value[5] = {0, 3, 4, 5, 6}; // 0 ：不选
int dp[5][9] = {0}; // 放总价的矩阵 初始化全0矩阵 (背包容量为8： 0~8 共9列)
int object[5];

void dpMax();  // 动态规划找能装下且价值最高解
void find(int i, int j);  // 回溯找回装了哪些物品
int max(int a, int b);  // 找最大值函数
void outDP();

int main() {

dpMax();
	printf("--------n");
	outDP();
	printf("--------n");
	find(4, 8);  // dp矩阵从[0][0]到[4][8]  即返回矩阵右下角格子

return 0;
}

void dpMax() {

// 从矩阵左上角向右下角计算，每次计算都会用到已有结果的上一排/上一列的值
	// 但矩阵第一行/第一列是出口，已经有值(为0)。即依旧从后往前选
	for (int i = 1; i < 5; i++) {
		for (int j = 1; j < 9; j++) {
			if (weight[i] > j) {  // 物品重量比背包剩下重量大，不选
				dp[i][j] = dp[i - 1][j];
				printf("dp[%d][%d] = %d ", i, j, dp[i][j]);
			} else {
				int A = value[i] + dp[i - 1][j - weight[i]]; // 选
				int B = dp[i - 1][j];  // 不选
				dp[i][j] = max(A, B);  // 选与不选中总价大的
				printf("dp[%d][%d] = %d ", i, j, dp[i][j]);
			}
		}
		printf("n");
	}
}

int max(int a, int b) {

return a > b ? a : b;
}

// 递归写法
// 回溯 从矩阵最右下角往左上角推
void find(int i, int j) {

printf("定位到 dp[%d][%d]n", i, j);

if (i == 0) {   // 先写递归出口,已经从右下角找到左上角
		for (int k = 0; k < 5; k++) {
			printf("%d ", object[k]);
		}
		return ;

}
	if (dp[i][j] == dp[i - 1][j]) { // 没装
		object[i] = 0;
		find(i - 1, j); // 往上移一个

} else if (dp[i][j] == dp[i - 1][j - weight[i]] + value[i] ) { // 装了
		object[i] = 1;
		find(i - 1, j - weight[i]);
	}

}

// 打印dp
void outDP() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			printf("dp[%d][%d] = %d ", i, j, dp[i][j]);
		}
		printf("n");
	}
}

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

# include <stdio.h>
# include <stdlib.h>

int weight[5] = {0, 2, 3, 4, 5}; // 0 ：背包容量已用完
int value[5] = {0, 3, 4, 5, 6}; // 0 ：不选
int dp[5][9] = {0}; // 放总价的矩阵 初始化全0矩阵 (背包容量为8： 0~8 共9列)
int object[5];

void dpMax();  // 动态规划找能装下且价值最高解
void find(int i, int j);  // 回溯找回装了哪些物品
int max(int a, int b);  // 找最大值函数
void outDP();

int main() {

	dpMax();
	printf("--------n");
	outDP();
	printf("--------n");
	find(4, 8);  // dp矩阵从[0][0]到[4][8]  即返回矩阵右下角格子

	return 0;
}

void dpMax() {

	// 从矩阵左上角向右下角计算，每次计算都会用到已有结果的上一排/上一列的值
	// 但矩阵第一行/第一列是出口，已经有值(为0)。即依旧从后往前选
	for (int i = 1; i < 5; i++) {
		for (int j = 1; j < 9; j++) {
			if (weight[i] > j) {  // 物品重量比背包剩下重量大，不选
				dp[i][j] = dp[i - 1][j];
				printf("dp[%d][%d] = %d ", i, j, dp[i][j]);
			} else {
				int A = value[i] + dp[i - 1][j - weight[i]]; // 选
				int B = dp[i - 1][j];  // 不选
				dp[i][j] = max(A, B);  // 选与不选中总价大的
				printf("dp[%d][%d] = %d ", i, j, dp[i][j]);
			}
		}
		printf("n");
	}
}

int max(int a, int b) {

	return a > b ? a : b;
}

// 递归写法
// 回溯 从矩阵最右下角往左上角推
void find(int i, int j) {

	printf("定位到 dp[%d][%d]n", i, j);

	if (i == 0) {   // 先写递归出口,已经从右下角找到左上角
		for (int k = 0; k < 5; k++) {
			printf("%d ", object[k]);
		}
		return ;

	}
	if (dp[i][j] == dp[i - 1][j]) { // 没装
		object[i] = 0;
		find(i - 1, j); // 往上移一个

	} else if (dp[i][j] == dp[i - 1][j - weight[i]] + value[i] ) { // 装了
		object[i] = 1;
		find(i - 1, j - weight[i]);
	}

}

// 打印dp
void outDP() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			printf("dp[%d][%d] = %d ", i, j, dp[i][j]);
		}
		printf("n");
	}
}