0-1背包问题是对空间问题，排布选择问题的抽象
所谓0-1标识的一个物体的两种状态，可以通俗的理解为一个物体是否放入背包内，放入为1，取出为0；
例如有题目有体积为1，2，3，4的四个物体，放入容积为5的背包，有几种方法？
又如输入两个整数m, n，要求找到所有小于n且和为m的所有组合？
都可简化为0-1背包问题，可归纳如下：
输入条件：
1-可累加对象的集合A{....}
2-对象的广义和sum
输出：
列出A的所有满足广义和为sum的子集
解决这类问题就是建立标记数组 BagArray
void bagProb(A,sum)
{
foreach(elm in A) //由大到小遍历集合A
{
if(elm<sum)
{
BagArray[index]=1;//放入背包
batProb(A^b, sum-elm)
BagArray[index]=0;//回溯
}
else if(elm==sum)
{
BagArray[index]=1;//放入背包
printArray(BagArray);
BagArray[index]=0;//回溯
}
}
}
以下是0-1背包其中一个问题的C++实现
1
#include "stdafx.h"
2
/**//************************************************************************/
3/**//* 0-1背包问题
4
输入两个整数m, n，要求找到所有小于n且和为m的所有组合 */
5/**//************************************************************************/
6int length=0;
7void PrintBag(BYTE bag[])
8
{
9
for(int i=1;i<=length;i++)
10
{
11 if(bag[i]==1)
12 cout<<i<<" ";
13
}
14 cout<<endl;
15}
16void BagProblem(int m,int n,BYTE bag[])
17{
18 if (n<1)
19 return;
20
21 if (n<m)
22 {
23 for (int i=n;i>0;i--)
24 {
25 bag[i]=1;
26 BagProblem(m-i,i-1,bag);
27 bag[i]=0;
28 }
29 }
30 else if(m==n)
31 {
32 bag[n]=1;
33 PrintBag(bag);
34 bag[n]=0;
35 BagProblem(m,n-1,bag);
36 }
37 else
38 {
39 BagProblem(m,m,bag);
40 }
41}
42void bag(int m,int n)
43{
44 if (n>m)
45 {
46 n=m;
47 }
48 BYTE *bag=new BYTE[n+1];
49 memset(bag,0,n+1);
50 length=n;
51 BagProblem(m,n,bag);
52 delete bag;
53}