配套作业——动态规划

需求

• 动态规划的方法编程实现01背包问题

• 给定实例：n=3，c=30, w=[16,15,15], p=[45,25,25]。画出动态规划解决该01背包问题实例的记录表填表过程。

• 动态规划实现矩阵连乘问题（选做）

实现

01背包问题

• 代码实现
• 测试运行

#include<iostream>

#include<algorithm>
using namespace std;

const int N = 10100;
int n;						//物品数量
int maxWeight;				//背包最大承重
int value[N];				//记录每个物品价值的数组
int weight[N];				//记录每个物品重量的数组
int bestValue[N][N];		//记录最大价值

int main() {

	cout << "请输入书包最大承重weight和数量n" << endl;
	cin >> maxWeight >> n;
	cout << "请输入每个物品的重量和价值" << endl;
	for (int i = 1; i <= n; i++) cin >> weight[i] >> value[i];

	//i 是物品编号 j是承重
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= maxWeight; j++) { 
			//装不下第i件物品，bestValue的价值跟i-1时一样
			if (j < weight[i]) bestValue[i][j] = bestValue[i - 1][j];
			//能装下则判断，装下的价值不装哪个更大，选出最优解
			else bestValue[i][j] = max(bestValue[i - 1][j], bestValue[i - 1][j -weight[i]] + value[i]);
			// 完全背包：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
		}

	
	cout <<"最大价值是： "<< bestValue[n][maxWeight] << endl;
	return 0;
}

手写动态规划

	0	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
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	45	45	45	45	45	45	45	45	45	45	45	45	45	45	45
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	25	45	45	45	45	45	45	45	45	45	45	45	45	45	45	45
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	25	45	45	45	45	45	45	45	45	45	45	45	45	45	45	50