01背包
0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
更具体的，抽象问题为：
有n个可选项，价值为vi，耗费wi，在总耗费为C的情况下选取，求总价值最大
使用dp[i][j]表示面对第i个可选项，耗费为j时所能取到的最大值，面临的只有两种选择，取当前项，或者不取当前项：

$dp[i][j]=\begin{cases}dp[i-1][j],             &\text j<wi \\ max(dp[i][j-wi]+vi,dp[i-1][j])    &\text j>=wi    \end{cases}$

自底向上遍历，先遍历物品，再遍历耗费，相当于先记录下来了底层物品，低容量的记录，顶层知道记录，因此可以快速做出判断。
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(j>=w[i])
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
            else
                m[i][j]=m[i-1][j];
        }
    }

需要注意的是，任何动归实现时都要注意边界条件与底层条件的设置，一定要符合公式的语义
确定能获取最大价值的选择项
另起一个 x[ ] 数组，x[i]=0表示不拿，x[i]=1表示拿。m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样，则x[n]=0 ; 否则 x[n]=1。当x[n]=0时，由m[n-1][c]继续构造最优解；当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解。以此类推，这种方式只能获取一个最优解。
    for(int i=n;i>1;i--)
    {
        if(m[i][c]==m[i-1][c])
            x[i]=0;
        else
        {
            x[i]=1;
            c-=w[i];//向下寻找
        }
    }
    x[1]=(m[1][c]>0)?1:0;//只剩下最后一个了，判断是否能拿即可

01背包

问题描述：给定 n 种物品和一背包，物品 i 的重量是 wi，其价值是 vi，背包容量为 c，问应如何选择装入背包中的物品，使装入背包中的物品价值最大?

回溯法

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入其左子树。当右子树中可能包含最优解时才进入右子树搜索。设 r 是当前剩余物品的价值总和；cv 是当前价值；max 是当前最优价值。当 cv + r <= max 时， 可减去右子树。



void BackTrack(int cw, int cv, int i) {
    if (i > n) {
        max = cv;
        return;
    }

    if (cw + w[i] <= c)
        BackTrack(cw + w[i], cv + v[i], i + 1);
    if (cv + r[i + 1]  >  max)
        BackTrack(cw, cv, i + 1);
}


void Init() {
    for (int i = n; i >= 1; i--)        
        r[i] = r[i + 1] + v[i];
}

动态规划（递推法）

正常的状态定义 d(i,j) = max{d(i+1,j), d(i+1,j-W[i]) + V[i]} 

d(i,j) 表示当前在第 i 层，背包剩余容量为 j 时的最大价值和，边界是 i > n 时 d(i,j) = 0;



for (int i = n; i >= 1; i--)
    for (int j = 0; j <= c; j++) {
        d[i][j] = (i == n ? 0 : d[i+1][j]);
        if (j >= W[i])
            d[i][j] = max(d[i][j], d[i+1][j-W[i]] + V[i]);
    }

对称的状态定义 f(i,j) = max{f(i-1,j), f(i-1,j-W[i]) + V[i]} 

f(i,j) 表示把前 i 个物品装到容量为 j 的背包中的最大价值和，边界是 i= 0 时 f(i,j) = 0;



for (int i = 1; i <= n; i++)
    for (int j = 0; j <= c; j++) {
        f[i][j] = (i == 1 ? 0 : f[i-1][j]);
        if (j >= W[i])
            f[i][j] = max(f[i][j], f[i-1][j-W[i]] + V[i]);
    }

边读边计算, 不必把 V 和 W 保存下来



for (int i = 1; i <= n; i++) {
    scanf("%d%d", &V, &W);
    for (int j = 0; j <= c; j++) {
        f[i][j] = (i == 1 ? 0 : f[i-1][j]);
        if (j >= W)
            f[i][j] = max(f[i][j], f[i-1][j-W] + V);
    }
}

滚动数组， 把数组 f 变成一维的



memset(f, 0,  sizeof(f));
for (int i = 1; i <= n; i++) {
    scanf("%d%d", &V, &W);
    for (int j = 0; j <= c; j++)
        if (j >= W)
            f[j] = max(f[j], f[j-W] + V);
}

问题描述

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8

i（物品编号）
			
1
			
2
			
3
			
4
		
w（体积）
			
2
			
3
			
4
			
5
		
v（价值）
			
3
			
4
			
5
			
6
		
 

总体思路

根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。

动态规划的原理

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。

背包问题的解决过程

在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
	
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

由此可以得出递推关系式：

j<w(i)      V(i,j)=V(i-1,j)
	
j>=w(i)     V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝
这里需要解释一下，为什么能装的情况下，需要这样求解（这才是本问题的关键所在！）：

可以这么理解，如果要到达V(i,j)这一个状态有几种方式？

肯定是两种，第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理（上文讲到），V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。

4、填表，首先初始化边界条件，V(0,j)=V(i,0)=0；



然后一行一行的填表：

如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
	
又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
	
如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10……
所以填完表如下图：



5、表格填完，最优解即是V(number,capacity)=V(4,8)=10。

 

代码实现

为了和之前的动态规划图可以进行对比，尽管只有4个商品，但是我们创建的数组元素由5个。

#include<iostream>
using namespace std;
#include <algorithm>

int main()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
	int bagV = 8;					        //背包大小
	int dp[5][9] = { { 0 } };			        //动态规划表

	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}

	//动态规划表的输出
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}

	return 0;
}

 

背包问题最优解回溯

通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：

V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
	
V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
	
一直遍历到i＝0结束为止，所有解的组成都会找到。
就拿上面的例子来说吧：

最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；
	
有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；
	
而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；
	
有V(1,0)=V(0,0)=0，所以第1件商品没被选择。


 

代码实现

背包问题最终版详细代码实现如下：

#include<iostream>
using namespace std;
#include <algorithm>

int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
int bagV = 8;					        //背包大小
int dp[5][9] = { { 0 } };			        //动态规划表
int item[5];					        //最优解情况

void findMax() {					//动态规划
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
}

void findWhat(int i, int j) {				//最优解情况
	if (i >= 0) {
		if (dp[i][j] == dp[i - 1][j]) {
			item[i] = 0;
			findWhat(i - 1, j);
		}
		else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
			item[i] = 1;
			findWhat(i - 1, j - w[i]);
		}
	}
}

void print() {
	for (int i = 0; i < 5; i++) {			//动态规划表输出
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;

	for (int i = 0; i < 5; i++)			//最优解输出
		cout << item[i] << ' ';
	cout << endl;
}

int main()
{
	findMax();
	findWhat(4, 8);
	print();

	return 0;
}



 

01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。
01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。

Pi表示第i件物品的价值。

决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？



题目描述：
假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？


name
weight
value
1
2
3
4
5
6
7
8
9
10
a
2
6
0
6
6
9
9
12
12
15
15
15
b
2
3
0
3
3
6
6
9
9
9
10
11
c
6
5
0
0
0
6
6
6
6
6
10
11
d
5
4
0
0
0
6
6
6
6
6
10
10
e
4
6
0
0
0
6
6
6
6
6
6
6

只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。

首先要明确这张表是至底向上，从左到右生成的。

为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。

对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。

同理，c2=0，b2=3,a2=6。

对于承重为8的背包，a8=15,是怎么得出的呢？

根据01背包的状态转换方程，需要考察两个值，
一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；
在这里，
 f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值

f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值

f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6

由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包

以下是actionscript3 的代码

		public function get01PackageAnswer(bagItems:Array,bagSize:int):Array
		{
			var bagMatrix:Array=[];
			var i:int;
			var item:PackageItem;
			for(i=0;i<bagItems.length;i++)
			{
				bagMatrix[i] = [0];
			}
			for(i=1;i<=bagSize;i++)
			{
				for(var j:int=0;j<bagItems.length;j++)
				{
					item = bagItems[j] as PackageItem;
					if(item.weight > i)
					{
						//i背包转不下item
						if(j==0)
						{
							bagMatrix[j][i] = 0;
						}
						else
						{
							bagMatrix[j][i]=bagMatrix[j-1][i];
						}
					}
					else
					{
						//将item装入背包后的价值总和
						var itemInBag:int;
						if(j==0)
						{
							bagMatrix[j][i] = item.value;
							continue;
						}
						else
						{
							itemInBag = bagMatrix[j-1][i-item.weight]+item.value;
						}
						bagMatrix[j][i] = (bagMatrix[j-1][i] > itemInBag ? bagMatrix[j-1][i] : itemInBag)
					}
				}
			}
			//find answer
			var answers:Array=[];
			var curSize:int = bagSize;
			for(i=bagItems.length-1;i>=0;i--)
			{
				item = bagItems[i] as PackageItem;
				if(curSize==0)
				{
					break;
				}
				if(i==0 && curSize > 0)
				{
					answers.push(item.name);
					break;
				}
				if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)
				{
					answers.push(item.name);
					curSize -= item.weight;
				}
			}
			return answers;
		}





PackageItem类


	public class PackageItem
	{
		public var name:String;
		public var weight:int;
		public var value:int;
		public function PackageItem(name:String,weight:int,value:int)
		{
			this.name = name;
			this.weight = weight;
			this.value = value;
		}
	}


测试代码


				var nameArr:Array=['a','b','c','d','e'];
				var weightArr:Array=[2,2,6,5,4];
				var valueArr:Array=[6,3,5,4,6];
				var bagItems:Array=[];
				for(var i:int=0;i<nameArr.length;i++)
				{
					var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);
					bagItems[i]=bagItem;
				}
				var arr:Array = ac.get01PackageAnswer(bagItems,10);