动态规划实验 0-1背包问题 代码+流程图

1.实验内容 0-1背包问题：若有物品n个，每个物品的价值Value，用vi表示，每个物品的重量weight用wi表示，其中vi和wi均为非负数。设背包的总容量为W，且W为非负数。现需要考虑的问题是：如何选择装入背包的物品，使装入背包的物品总价值最大。

【动态规划解步骤】 第一步，刻画问题的最优解子结构。可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即xn=1，那么其余x1，x2，…，x(n-1)一定构成子问题1，2，…，n-1在容量W-wn时的最优解。如果这个最优解不包含物品n，即xn=0，那么其余x1，x2，…，x(n-1)一定构成子问题1，2，…，n-1在容量W时的最优解。

第二步，递归定义最优解的值，根据上述分析的最优解的结构递归地定义问题最优解。设G[i,w]表示背包容量为w时，i个物品导致的最优解的总价值，得到下式。显然要求G[n,w]：

2.算法流程图及说明

3.核心代码解释

/*
c[i][w]表示背包容量为w时，i个物品导致的最优解的总价值，大小为(n+1)*(w+1)
v[i]表示第i个物品的价值，大小为n
w[i]表示第i个物品的重量，大小为n
*/
#include <iostream>
using namespace std;
void Dny(int n, int W, int c[][18], int* v, int* wei)//构建最优解子结构
{
          
   
	memset(*c, 0, (W + 1) * sizeof(int));
	for (int i = 1; i <= n; i++)//构建最优子结构从装入一个物品开始
	{
          
   
		c[i][0] = 0;
		for (int w = 1; w <= W; w++)
		{
          
   
			if (wei[i - 1] > w)	//此处比较是关键，当当前第一个物品重量大于当前背包容量时，最优子结构等于上一所装数量的最优解
			{
          
   
				c[i][w] = c[i - 1][w];
			}
			else//否则可以装入
			{
          
   
				int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];	//注意wei和v数组中的第i个应该为wei[i-1]和v[i-1]
				if (c[i - 1][w] > temp)//如果上一个最优子结构大于当前价值，则不装，否则装入。
				{
          
   
					c[i][w] = c[i - 1][w];
				}
				else
					c[i][w] = temp;//写入当前最优解
			}
		}
	}
}

void assign(int c[][18], int* x, int* wei, int n, int W)
{
          
   
	int w = W;
	for (int i = n; i >= 2; i--)
	{
          
   
		if (c[i][w] == c[i - 1][w])
		{
          
   
			x[i - 1] = 0;
		}
		else
		{
          
   
			x[i - 1] = 1;
			w = w - wei[i - 1];
		}
	}
	if (c[1][w] == 0)
		x[0] = 0;
	else
		x[0] = 1;
}

int main()
{
          
   
	int n = 5;
	int W = 17;
	int w[] = {
          
    3, 4, 7, 8, 9 };
	int v[] = {
          
    4, 5, 10, 11, 13 };
	int c[6][18] = {
          
    0 };
	Dny(n, W, c, v, w);
	cout << c[5][17] << endl;
	int x[5];
	assign(c, x, w, n, W);
	cout << "Here is the assignment!" << endl;
	for (int i = 0; i < n; i++)
		cout << x[i] << endl;
	for (i = 0; i <= n; i++)
	{
          
   
		for (int j = 0; j <=W; j++)
			cout << c[i][j] << "   ";
		cout << endl;
	}
	return 0;
}

if (wei[i - 1] > w)	
	c[i][w] = c[i - 1][w];
else
	int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];

然后构建表格！当运行到装下一个物品的时候，判断上一个物品是放着还是取出！