DP学习_0-1背包问题

问题描述：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

算法分析：

DP的问题可以转化为一种维护备忘录（表）的思想，0-1背包问题是DP的基本问题，其本质在于自底向上地维护下面所示的一张表：

案例假设：n=3; c=6;

物品的重量w与价值v如下：

物品	0	1	2
w	3	2	1
v	3	2	1

程序要维护的表（人工算出）：

i j	1	2	3	4	5	6
2	1	1	1	1	1	1
1	1	2	3	3	3	3
0	1	2	3	4	5	6

维护过程说明：

首先在初始化时提供i=2这一行的值，程序运行时遵循以下原则：

1. 当i=n-1时，若j>=w[i],则m(i,j)=v[i]；若0<=j<w[i]，则m(i,j)=0
2. 当i<n-1时，若j>=w[i],则m(i,j)=max{ m(i+1,j), m(i+1,j-w[i])+v[i] }；若0<=j<w[i]，则m(i,j)=m(i+1,j)

对于这个规则的分析：

【m(i+1,j) 容量为j，不新添加第i个物品时的最大价值】

【m(i+1,j-wi)+v[i] 容量j去掉第i个物品质量时的最大值（表中在之前已经求出）直接加上v[i]，即强制添加第i个物品】

【需要添加i的情况的剪贴法解释：强制添加第i物品比不添加，总价值更高】

根据以上分析产生的代码：

//0-1 Knapsack problem 
#include <iostream>
#include <vector>
using std::cout;
using std::vector;
using std::cin;
using std::endl;

#define MAX_KNAPSACK 10
#define MAX_CONTAIN 50

class KPC
{
private:
	int v[MAX_KNAPSACK];//Value
	int w[MAX_KNAPSACK];//Weight
	int f[MAX_KNAPSACK][MAX_CONTAIN];//Best Value
	vector<int> item[MAX_KNAPSACK][MAX_CONTAIN];//Item List
	int c;//Contain
	int n;//Item Size
public:
	void DP();//物品起始号，当前容量
	void PrintVector(vector<int> vect);//打印某一格的物品清单
};

void KPC::PrintVector(vector<int> vect)
{
	if(vect.begin() == vect.end()) return;
	vector<int>::iterator it;
	for(it=vect.begin(); it!=vect.end()-1; it++)
	{
		cout << *it;
		cout << ".";
	}
	cout << *it;
}

void KPC::DP()
{
	cin >> n >> c;//先输入物品数，然后是容量
	for(int i=0; i!=n; i++)
	{
		cin >> w[i] >> v[i];//先重量，后价值
	}

	//初始化的值将作为基点
	//空的部分
	int min = w[n-1] < c ? w[n-1] : c;
	int j=0;
	for(; j<min; j++)
	{
		f[n-1][j] = 0;
	}
	//有物部分的第一行
	for(; j<=c; j++)
	{
		f[n-1][j] = v[n-1];
		item[n-1][j].push_back(n-1);
	}

	for(int j = 0; j <= c; j++)//按上到下、左到右顺序填表
	{
		for(int i=n-2; i>=0; i--)//总质量一定，找到最优值
		{
			if(j < w[i])
			{
				for(int t=j; t<=w[i]; t++)
				{
					f[i][t] = f[i+1][j];
					item[i][j] = item[i+1][j];//继承
				}
			}
			else//j == w[i]
			{
				if(f[i+1][j] > f[i+1][j-w[i]] + v[i])
				{
					f[i][j] = f[i+1][j];
					item[i][j] = item[i+1][j];//继承
				}
				else
				{
					f[i][j] = f[i+1][j-w[i]] + v[i];
					item[i][j] = item[i+1][j-w[i]];
					item[i][j].push_back(i);//添加新物品
				}
			}
		}
	}

	//输出右下角的值作为最大价值的解
	cout << f[0][c] << endl;
	//物品的解
	PrintVector(item[0][c]);
	cout << endl;
	//打印填好的价值表
	for(int i=n-1; i>=0; i--)
	{
		for(int j=0; j<=c; j++)
		{
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	cout << "-------------------" << endl;
	//打印填好的物品表
	for(int i=n-1; i>=0; i--)
	{
		for(int j=0; j<=c; j++)
		{
			cout << "[";
			PrintVector(item[i][j]);
			cout << "]";
		}
		cout << endl;
	}
}

int main()
{
	KPC KP;
	KP.DP();
	system("pause");
}

运行结果：

3 6

3 3
2 2
1 1

6
2.1.0
0 1 1 1 1 1 1
0 1 2 3 3 3 3
0 1 2 3 4 5 6
-------------------
[][2][2][2][2][2][2]
[][2][1][2.1][2.1][2.1][2.1]
[][2][1][0][2.0][1.0][2.1.0]
Press any key to continue . . .

5 10

1 10
3 5
2 6
9 8
4 7

28
4.2.1.0
0 0 0 0 7 7 7 7 7 7 7
0 0 0 0 7 7 7 7 7 8 8
0 0 6 6 7 7 13 13 13 13 13
0 0 6 6 7 11 13 13 13 18 18
0 10 10 16 16 17 21 23 23 23 28
-------------------
[][][][][4][4][4][4][4][4][4]
[][][][][4][4][4][4][4][3][3]
[][][2][2][4][4][4.2][4.2][4.2][4.2][4.2]
[][][2][2][4][2.1][4.2][4.2][4.2][4.2.1][4.2.1]
[][0][0][2.0][2.0][4.0][2.1.0][4.2.0][4.2.0][4.2.0][4.2.1.0]
Press any key to continue . . .

秒客网

DP学习_0-1背包问题

相关文章