【算法概论】动态规划：背包问题

0 - 1背包问题

问题描述：

       给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为W（假定物品重量与背包容量值均为整数），应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？设计一个动态规划算法，求解背包问题。

❗算法描述❗：

定义 w[] 存储各物品的重量，v[] 存储各物品的价值，背包的重量为 wsum。

①定义子问题：

       k(w, j) = 容量剩余 w 时，从物品 1 到 j 能得到的最高价值。

②是否满足最优子结构：

       k(w, j) = max( k(w - wj, j-1) + vj，k(w, j-1))；

       前者指，第 j 个物品放入背包中，则产生的最高价值就是，在背包容量为 w-wj的情况下，在 0 ~ j-1 这些物品中能产生的最高价值 + 第 j 个物品 的价值；

       后者指，第 j 个物品不放入背包中，则产生的最高价值就是，背包容量还剩 w，在0 ~ j-1 这些物品中能产生的最高价值。

       所以，

          |    0, if w == 0 or j = 0
k(w, j) = |    k(w, j-1), if w < wj
          |    max( k( w - wj, j - 1) + vj, k(w, j-1)), otherwise

③确定解决子问题的次序：

       自底向上,bottom - up。

④回溯最优解：

代码如下：

#include <iostream>
#include <vector>

using namespace std;

int max(int, int);
void knapsack(vector<vector<int>> k, vector<int> w, vector<int> v, int c, int num);

int main()
{
	int num;
	cout << "请输入物品个数:" << endl;
	cin >> num;

	vector<int> w(num + 1, 0);
	vector<int> v(num + 1, 0);
	cout << "请输入各物品的重量:" << endl;
	for (int i = 1; i < num + 1; ++i)
	{
		cin >> w[i];
	}
	cout << "请输入各物品的价值:" << endl;
	for (int i = 1; i < num + 1; ++i)
	{
		cin >> v[i];
	}

	int c;
	cout << "请输入背包的容量:" << endl;
	cin >> c;

	vector<vector<int>> k(c + 1, vector<int>(num + 1));

	for (int i = 0; i < c; ++i)
	{
		k[i][0] = 0;
	}
	for (int j = 0; j < num; ++j)
	{
		k[0][j] = 0;
	}

	for (int j = 1; j < num + 1; ++j)
	{
		for (int i = 0; i < c + 1; ++i)
		{
			//如果背包的剩余容量小于第 j 个物品的重量
			if (i < w[j])
			{
				k[i][j] = k[i][j - 1];
			}
			//否则
			else
			{
				k[i][j] = max(k[i - w[j]][j - 1] + v[j], k[i][j - 1]);
			}
		}
	}

	cout << "背包可能容纳物品的最大价值:" << endl;
	cout << k[c][num] << endl;

	knapsack(k, w, v, c, num);
	cout << endl;

	return 0;
}

//回溯结果
void knapsack(vector<vector<int>> k, vector<int> w, vector<int> v, int c, int num)
{
	if (c >= w[1] && num > 0)
	{
		if (k[c][num] == k[c - w[num]][num - 1] + v[num])
		{
			cout << num << ' ';
			knapsack(k, w, v, c - w[num], num - 1);
		}
		else if (k[c][num] == k[c][num - 1])
		{
			knapsack(k, w, v, c, num - 1);
		}
	}
	else
	{
		return;
	}
}

int max(int a, int b)
{
	return a > b ? a : b;
}

一篇有趣的讲解：https://www.jianshu.com/p/a66d5ce49df5

一篇全面的讲解：https://wenku.baidu.com/view/fa370577ae1ffc4ffe4733687e21af45b307fe7a.html