问题模板      
 
 01背包，有件物品和一个容量为V的背包。放入第件物品耗费的费用是,得到的价值是。求解将哪些物品装入背包可使价值总和最大。     
 
例题 
 
采药
 
思路
 
对于01背包问题中的每一种物品都有取或不取两种选择：取或不取。对于子问题定义状态：即表示前件物品恰好放入一个容器为的背包可以获得的最大价值。则其状态转移方程为：
 
                                            
 
源码
 
内存不压缩版本：
 
#include<iostream>
using namespace std;

#define ll long long

const int MAXN=111;
int t,m; 
int a[MAXN],b[MAXN];
int f[1010][1010];
int read(){
	int f=1,ans=0;
	char c;
	c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return f*ans;
}
int main() {

	t=read();
	m=read();
	for(int i=1;i<=m;i++) a[i]=read(),b[i]=read();
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			if(j>=a[i]){
				f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
			}else{
				f[i][j]=f[i-1][j];
			}
		}
	}
	cout<<f[m][t];	
	return 0;
}
 
内存压缩版本：
 
#include<iostream>

using namespace std;

const int MAXN=111;

int t,m; 
int a[MAXN],b[MAXN];
int f[1010];
int read(){
	int f=1,ans=0;
	char c;
	c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return f*ans;
}
int main() {
	t=read();
	m=read();
	for(int i=1;i<=m;i++) a[i]=read(),b[i]=read();
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			if(j>=a[i]){
				f[j]=max(f[j],f[j-a[i]]+b[i]);
			}
		}
	}
	cout<<f[t];	
	return 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背包问题
 
1、问题描述
 
　　给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ （要求使用回溯法）
 
　例如：
 
 
２、算法分析
 
【整体思路】
 
　　01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。
 
      在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。
 
　　上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。　
 
   　为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。
 
【举例说明】
 
　　对于n=4的0/1背包问题，其解空间树如图所示，树中的16个叶子结点分别代表该问题的16个可能解。 
 
 
【算法设计】
 
    利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi （即对n个物品放或不放的一种的方案）
 
　其中， (ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包）。
 
在递归函数Backtrack中，
 　　　　当i>n时，算法搜索至叶子结点，得到一个新的物品装包方案。此时算法适时更新当前的最优价值
 　　　　当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
 
【时间复杂度&&优化】　　
 
　　因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为。
 
　　因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。
 
相关链接１
 
相关链接２
 
相关链接３
 
【源代码】        
 
#include <iostream>
#include <stdio.h>
//#include <conio.h>
using namespace std;
int n;//物品数量
double c;//背包容量
double v[100];//各个物品的价值　value
double w[100];//各个物品的重量　weight
double cw = 0.0;//当前背包重量　current weight
double cp = 0.0;//当前背包中物品总价值　current value
double bestp = 0.0;//当前最优价值best price
double perp[100];//单位物品价值(排序后) per price
int order[100];//物品编号
int put[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据


//按单位价值排序
void knapsack()
{
    int i,j;
    int temporder = 0;
    double temp = 0.0;

    for(i=1;i<=n;i++)
        perp[i]=v[i]/w[i]; //计算单位价值（单位重量的物品价值）
    for(i=1;i<=n-1;i++)
    {
        for(j=i+1;j<=n;j++)
            if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
        {
            temp = perp[i];  //冒泡对perp[]排序
            perp[i]=perp[j];
            perp[j]=temp;

            temporder=order[i];//冒泡对order[]排序
            order[i]=order[j];
            order[j]=temporder;

            temp = v[i];//冒泡对v[]排序
            v[i]=v[j];
            v[j]=temp;

            temp=w[i];//冒泡对w[]排序
            w[i]=w[j];
            w[j]=temp;
        }
    }
}

//回溯函数
void backtrack(int i)
{   //i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品
    double bound(int i);
    if(i>n) //递归结束的判定条件
    {
        bestp = cp;
        return;
    }
    //如若左子节点可行，则直接搜索左子树;
    //对于右子树，先计算上界函数，以判断是否将其减去
    if(cw+w[i]<=c)//将物品i放入背包,搜索左子树
    {
        cw+=w[i];//同步更新当前背包的重量
        cp+=v[i];//同步更新当前背包的总价值
        put[i]=1;
        backtrack(i+1);//深度搜索进入下一层
        cw-=w[i];//回溯复原
        cp-=v[i];//回溯复原
    }
    if(bound(i+1)>bestp)//如若符合条件则搜索右子树
        backtrack(i+1);
}

//计算上界函数，功能为剪枝
double bound(int i)
{   //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值
    double leftw= c-cw;//剩余背包容量
    double b = cp;//记录当前背包的总价值cp,最后求上界
    //以物品单位重量价值递减次序装入物品
    while(i<=n && w[i]<=leftw)
    {
        leftw-=w[i];
        b+=v[i];
        i++;
    }
    //装满背包
    if(i<=n)
        b+=v[i]/w[i]*leftw;
    return b;//返回计算出的上界

}



int main()
{
    int i;
    printf("请输入物品的数量和背包的容量：");
    scanf("%d %lf",&n,&c);
    /*printf("请输入物品的重量和价值：\n");
    for(i=1;i<=n;i++)
    {
        printf("第%d个物品的重量：",i);
        scanf("%lf",&w[i]);
        printf("第%d个物品的价值是：",i);
        scanf("%lf",&v[i]);
        order[i]=i;
    }*/
    printf("请依次输入%d个物品的重量:\n",n);
    for(i=1;i<=n;i++){
        scanf("%lf",&w[i]);
        order[i]=i;
    }

    printf("请依次输入%d个物品的价值:\n",n);
    for(i=1;i<=n;i++){
        scanf("%lf",&v[i]);
    }


    knapsack();
    backtrack(1);


    printf("最优价值为：%lf\n",bestp);
    printf("需要装入的物品编号是：");
    for(i=1;i<=n;i++)
    {
        if(put[i]==1)
            printf("%d ",order[i]);
    }
    return 0;
}