0-1背包問題是對(duì)空間問題，排布選擇問題的抽象
所謂0-1標(biāo)識(shí)的一個(gè)物體的兩種狀態(tài)，可以通俗的理解為一個(gè)物體是否放入背包內(nèi)，放入為1，取出為0；
例如有題目有體積為1，2，3，4的四個(gè)物體，放入容積為5的背包，有幾種方法？
又如輸入兩個(gè)整數(shù)m, n，要求找到所有小于n且和為m的所有組合？
都可簡化為0-1背包問題，可歸納如下：
輸入條件：
1-可累加對(duì)象的集合A{....}
2-對(duì)象的廣義和sum
輸出：
列出A的所有滿足廣義和為sum的子集
解決這類問題就是建立標(biāo)記數(shù)組 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背包其中一個(gè)問題的C++實(shí)現(xiàn)
1
#include "stdafx.h"
2
/**//************************************************************************/
3/**//* 0-1背包問題
4
輸入兩個(gè)整數(shù)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}