动态规划 01背包问题

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

问题描述：

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

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

出口有 3 种：

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

物品编号  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");
	}
}

输出：

回溯

dp[ i ] [ j ] 与 dp[ i -1] [ j ] 上下不一样说明，第 i 个物品装入了背包

最后

以上就是专注蜡烛为你收集整理的动态规划 / 回溯算法【01背包问题】 （C语言）动态规划 01背包问题问题描述：回溯的全部内容，希望文章能够帮你解决动态规划 / 回溯算法【01背包问题】 （C语言）动态规划 01背包问题问题描述：回溯所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。