C语言：01背包算法

一、实验目的

1、熟悉C/C++语言的集成开发环境；

1、通过动态规划算法的示例程序理解动态规划算法的基本思想

2、运用动态规划算法解决实际问题加深对动态规划算法的理解和运用

二、实验内容

1、动态规划算法思想：

把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解，但动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始返回求解。动态规划求解问题的关键在于获得各个阶段子问题的递推关系式：

（1）分析原问题的最优解性质，刻画其结构特征

（2）递归定义最优值

（3）自底向上（由后向前）的方式计算最优值

（4）根据计算最优值时得到的信息，构造一个最优解。

2、0－1背包问题

有n件物品和一个容量为c的背包。第i件物品的容量是w[i]，价值是p[i]。求解将哪些物品装入背包可使价值总和最大。

//物品数量:5
//背包容量:承重20
//定义重量:0  2  3  4  5   9
//定义价值:0  3  4  5  8  10
#include
int B[6][21] = { 0 };//背包可以装6个 承重21
int W[6] = { 0, 2, 3, 4, 5, 9 };
int V[6] = { 0,3,4,5,8,10 };
int choose[6];

int max(int a, int b) {//大小比较
	return (a > b ? a : b);
}
void solo() {//背包算法核心部分
	for (int i = 1; i < 6; i++) {//i为当前可选物品数
		for (int j = 1; j < 21; j++) {//j为当前可承重量
			if (W[i] > j) {
				B[i][j] = B[i-1][j];//不偷
			}
			else {
				B[i][j]=max(B[i - 1][j], B[i - 1][j-W[i]] + V[i]);//偷与不偷比较

			}
		}
	}
}
void fine() {//输出最佳的选择
	int i = 5;
	int j = 20;
	while (i!=0) {
		if (B[i][j] != B[i - 1][j]) {//如果i选择和i-1的选择不等则已偷，反则没有偷
			printf("选择了%d号物品n", i);
			j = j - W[i];
			i--;
		}
		else {
			i--;
		}
	}
}
int main() {
	solo();
	for (int i = 0; i < 6; i++) {//i为当前可选物品数
		for (int j = 0; j < 21; j++) {//j为当前可承重量
			printf("%3d", B[i][j]);
		}printf("n");
	}
	printf("n");
	fine();
	return 0;
}