0-1背包问题：

       有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

       这个问题的特点是：每种物品只有一件，可以选择放或者不放。

算法基本思想：

      利用动态规划思想 ，子问题为：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件物品的问题，即1、如果不放第i件物品，则问题转化为“前i-1件物品放入容量为v的背包中”；2、如果放第i件物品，则问题转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”(此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i])。则f[i][v]的值就是1、2中最大的那个值。

（注意：f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并一定是f[N] [V]，不一定是唯一的最大值，也可以是f[N][0..V]的最大值。

 以上概念和算法基本思想来源于blog：http://www.cnblogs.com/fly1988happy/archive/2011/12/13/2285377.html

以下为算法代码：是个不断优化的过程。首先(1)给出了递归和迭代的思想，(2)然后对迭代的算法代码进行空间优化。(3)然后给出了该问题的变种：恰好装满背包和完全背包问题。

(1)递归方法：

// 0-1 背包问题递归方法  回溯求最佳解
int packageRecursion(int c, int n)
{
	if(n == C) 
		return (c < weight[n])? 0 : value[n];
	if(c < weight[n]) 
		return packageRecursion(c, n+1);
	return max(packageRecursion(c, n+1), packageRecursion(c - weight[n], n+1) + value[n]);
}

(2)迭代方法：

//  0-1 背包问题迭代方法 
void packageIteraction()
{
	int **F;
	F = new int*[N+1];   // 申请内存空间
	int i;
	for(i = 0; i < N+1; i++)
	{
		F[i] = new int [C+1];
		
	}

	int j;
	for(i = 0 ; i < N+1; i++)
	{
		for(j = 0; j < C+1; j++)
		{
			F[i][j] = 0;              // 初始化
		}
	}

	// 正好装满背包 加上这几行
	/*for(i = 0 ; i < N+1; i++)
	{
		for(j = 1; j < C+1; j++)
		{
			F[i][j] = min;             
		}
	}*/


	for(i = 1; i < N+1; i++)
	{
		for(j = weight[i]; j < C+1; j++)
		{
			F[i][j] = F[i-1][j] > (F[i-1][j-weight[i]]+value[i])? F[i-1][j] : (F[i-1][j-weight[i]]+value[i]);
		}
	}
	if(F[N][C] > 0)
	{
		cout << "the opt value:" << F[N][C] << endl; 
		j = C;                //  回溯 遍历出所选择的节点
		for(i = N; i >= 1; i--)
		{
			if(F[i][j] == (F[i-1][j-weight[i]]+value[i]))
			{
				cout << i << "weight=: " << weight[i] << " value=http://www.mamicode.com/: "<< value[i] << endl;>
（3）迭代方法优化空间复杂度：
      以上迭代方法的时间复杂度和空间复杂度都是O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。此时的做法是用F[V]来存储当前获得的价值的最大值，第二个for循环反向遍历。
//  将j=V:weight[i] 只用一维数组保存就可以了，降低了空间复杂度
void packageIteractionOpt()
{

	int *F;
	F = new int[C+1];   // 申请内存空间
	int i;
	for(i = 0; i < C+1; i++)
		F[i] = 0;

	// 正好装满背包 加上这句
	/*for(i = 1; i < C+1; i++)      
		F[i] = min; */

	for(i = 1; i < N+1; i++)
	{
		for(int j= C; j >= weight[i]; j--)
		{
			F[j] = F[j] > (F[j-weight[i]]+value[i])? F[j] : (F[j-weight[i]]+value[i]);
		}
	}
	cout << F[C] << endl;

	delete []F;     // 释放内存空间
}
Main函数代码：
int main()
{
	cin >> C >> N;
	weight = new int[N+1];
	value = http://www.mamicode.com/new int[N+1];>
输出结果：

(4)变种
       1：恰好装满背包
       在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果不能恰好满足背包容量，即不能得到f[V]的最优值，则此时f[V]=-∞，这样就能表示没有找到恰好满足背包容量的最优值。
以上代码中可以将注释的部分加上就可以了。其中int类型中最小值为0x80000000.
       2：完全背包
  此问题来源于hihoCoder中：链接，即将背包只能兑换一次或者不兑换改为可以兑换无数次
/*完全背包问题 http://hihocoder.com/contest/hiho7/problem/1 */
#include <iostream>
#include <memory.h>    //A题时候使用memset需要添加这个库函数
using namespace std;
int main()
{
	int N, M;
	while(cin >> N >> M)
	{
		int need, value;
		int *F = new int[M+1];

		int i, j;
		memset(F, 0, sizeof(int)*(M+1));
		//for(i = 0; i < M+1; i++)
			//F[i] = 0;

		for(i = 1; i < N+1; i++)
		{
			cin >> need >> value;
			for(j = need; j<=M; j++)
			{
				F[j] = F[j] > (F[j-need]+value)?F[j]:(F[j-need]+value);
			}	
		}
		
		// 错误代码
		/*
		如样例 2 10 2 3 3 5
		*/
		/*int k;
		for(i = 1; i < N+1; i++)
		{
			cin >> need >> value;
			for(j = M; j>=need; j--)
			{
				if(need == 0) k = 0;
				else k = j/need;   //  
				F[j] = F[j] > (F[j-k*need]+k*value)?F[j]:(F[j-k*need]+k*value);  
			}
		}*/
		cout << F[M] << endl;
		delete []F;
	}
}

// 测试输入
/*5 1000
144 990
487 436
210 673
567 58
1056 897*/

// 输出
// 5940
作者：小村长  出处：http://blog.csdn.net/lu597203933 欢迎转载或分享，但请务必声明文章出处。 （新浪微博：小村长zack, 欢迎交流！）
0-1背包问题及变种