深入浅出之背包算法——动态规划是如何打败递归的？

背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。这个问题涉及到了两个条件：一是物品总的大小小于或等于背包的大小，二是物品总的价值要尽量大。

一.采用递归的回溯法

刚开始接触此类问题时，很多人都会想到用回溯法解决，也就是用递归，这是最直接的方法，同八皇后、迷宫、组合、全排列、贪吃蛇等问题一样，下面给我本人开始用递归写出的算法：

//采用递归解决背包问题
#include "stdafx.h"
#include <Windows.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Fruit
{
private:
	string name;
	int size;
	int price;

public:
	Fruit(string name,int size,int price)
	{
		this->name=name;
		this->size=size;
		this->price=price;
	}
	string getName(){
		return name;
	}
	int getPrice(){
		return price;
	}
	int getSize(){
		return size;
	}
};

#define BOUNCE 10 //最大装入数量
#define N 10 //水果的个数

Fruit fruits[]={
	Fruit("李子", 4, 4500),
	Fruit("苹果", 5, 4700),
	Fruit("橘子", 2, 2250),
	Fruit("草莓", 1, 1100),
	Fruit("甜瓜", 6, 4940),
	Fruit("菠萝", 2, 3900),
	Fruit("西瓜", 6, 5800),
	Fruit("桃子", 3, 3700),
	Fruit("香蕉", 2, 3750),
	Fruit("梨子", 3, 3600)
};

vector<Fruit> selectedCompose; //当前最优选择序列
int maxPrice; //当前最大总价格

void Search(int begin, int sumSize, int sumPrice, vector<Fruit> v)
{
	for (int i = begin; i < N; i++)
	{
		int s = sumSize + fruits[i].getSize();
		int t = sumPrice + fruits[i].getPrice();
		if (s == BOUNCE) //当前背包的装入数量已经达到最大
		{
			v.push_back(fruits[i]);
			cout<<"总价值："<<t<<"\t";
			for (int i = 0; i < v.size(); i++) //把每种总量为N的组合都打印出来，方便测试
			{
				cout<<v[i].getName()<<"\t";
			}
			cout<<endl;
			if (t > maxPrice)
			{
				selectedCompose = v;//select始终是价格总数最大的那个组合
				maxPrice = t; //maxPrice始终存放最高总价格
			}
			v.pop_back();//将最后一个元素删除，以寻找下一个可能的匹配
		}
		if (s < BOUNCE)
		{
			v.push_back(fruits[i]);
			Search(i + 1, s, t, v); //递归
			v.pop_back();//回溯，要恢复递归之前得状态
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	vector<Fruit> v;
	maxPrice = 0;
	cout<<"所有总量为 "<<N<<"的组合为："<<endl;
	cout<<"------------------------------------------"<<endl;
	Search(0, 0, 0, v);
	cout<<"------------------------------------------"<<endl;
	cout<<"在总量为"<<N<<"的情况下，总价值最大的组合为："<<endl;
	for (int i = 0; i < selectedCompose.size(); i++)
	{
		cout<<selectedCompose[i].getName()<<"\t";
	}
	cout<<endl<<"总价值为： "<<maxPrice<<endl;
	system("pause");
	return 0;
}

基本原理很简单：求出满足总量的所有组合，再找出总价值最大的那个组合！

递归算法虽然方便，但是所需时间复杂度很高。该算法的时间复杂度为O(n2^n)

二.动态规划

动态规划方法建立在最优原则的基础上，是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些

结果减轻运算量。

如果我们用子问题定义状态来描述的话可以这样解释：

用f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。用公式表示:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

具体的解释可以理解为将前i件物品放入容量为v的背包中，现只考虑第i件物品的策略（放或不放），那么就可以转化为一个只涉及前i-1件物品和第i件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。（v表示背包的最大容量，c[i]表示第i件物品的大小，w[i]表示第i件物品的价值）

// KnapsackProblem.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <Windows.h>
#include <iostream>
#include <string>

using namespace std;

#define MAX 8
#define MIN 1

class Fruit
{
private:
	string name;
	int size;
	int price;

public:
	Fruit(string name,int size,int price)
	{
		this->name=name;
		this->size=size;
		this->price=price;
	}
	string getName(){
		return name;
	}
	int getPrice(){
		return price;
	}
	int getSize(){
		return size;
	}
};


void main()
{
	int item[MAX+1];
	int value[MAX+1];
	Fruit fruits[]={
		Fruit("李子", 4, 4500),
		Fruit("苹果", 5, 4700),
		Fruit("橘子", 2, 2250),
		Fruit("草莓", 1, 1100),
		Fruit("甜瓜", 6, 3700),
		Fruit("菠萝", 2, 4900),
		Fruit("西瓜", 3, 5800)
	};
	for (int i = 0; i < MAX+1; i++)
	{
		item[i] = 0;
		value[i] = 0;
	}
	
	for(int i = 0; i < 7; i++)
	{
		for(int s = fruits[i].getSize();s <= MAX; s++)
		{
			//s表示现在背包的大小
			int p = s-fruits[i].getSize(); //表示每次增加单位背包空间，背包所剩的空间
			int newvalue = value[p] + fruits[i].getPrice(); //value[p]表示增加的背包空间可以增加的价值，fruits[i].getprice()表示原有的背包的价值
			if(newvalue > value[s])
			{
				//现有的价值是否大于背包为s时的价值
				value[s] = newvalue;
				item[s] = i;//将当前的水果项添加到背包的物品中
			}
		}
	}
	cout<<"物品\t价格"<<endl;
	for(int i =  MAX; i > MIN; i = i - fruits[item[i]].getSize())
	{
		cout<<fruits[item[i]].getName() << "\t"<< fruits[item[i]].getPrice()<<endl;
	}
	cout<<"合计\t"<<value[MAX];

	system("pause");
}