1、環(huán)境配置：

• 系統(tǒng)：win10
• 編程語(yǔ)言：C++
• 編譯器：DevC++

2、問(wèn)題描述：

• 簡(jiǎn)單的0/1背包問(wèn)題：設(shè)一背包可容納物品的最大質(zhì)量為m，現(xiàn)有n件物品，質(zhì)量為m1，m2，...，mn，mi，均為正數(shù)，要從n件物品中挑選若干件，使放入背包的質(zhì)量之和不超過(guò)m。

3、算法思想：

思想：對(duì)于一個(gè)物品來(lái)說(shuō)，如果可以放到背包里，則有兩種選擇，一種是放，一種是不放。如果放不進(jìn)去，則不放，繼續(xù)下一個(gè)。
實(shí)現(xiàn)：用打印的方式打印出所有可能

分析.png

4、第一代代碼：

/*
《0/1背包問(wèn)題》
1、背包的重量被限制w
2、有一些物品，每個(gè)物品都有不同的重量
3、對(duì)于每個(gè)物品來(lái)說(shuō)，如果能裝進(jìn)去，可以選擇裝（1），
也可以選擇不裝（0）。 
*/

#include<iostream>

using namespace std;

int beibao(int w,int s,int e,int a[],int b[]); 

int main()
{
   int A[]={10,20,30};
   int B[]={0,0,0};
   cout<<"test:"<<sizeof(A)/sizeof(A[0])<<endl;
   
   beibao(50,0,2,A,B);
   
   return 0;
}



//打印所有可能的0/1背包問(wèn)題
int beibao(int w,int s,int e,int a[],int b[]){  
    
    if(s>e){
        cout<<"test:"<<sizeof(a)/sizeof(a[0])<<" ";
        for(int i=0; i<(sizeof(a)/sizeof(a[0])+1); i++)//這里為了能打印所有特意加1 
        {
            if(b[i]==1){
                cout<<a[i]<<",";
            }
            else{
                cout<<0<<",";
            }
        } 
        cout<<""<<endl;
        return 0;
    }
    
    if((w-a[s])>=0)//a[s]可以放進(jìn)去時(shí)，則放 
    {
        cout<<"能放則放"<<endl; 
        b[s]=1;
        beibao(w-a[s],s+1,e,a,b);
    }
    
    if((w-a[s])>=0)//a[s]可以放進(jìn)去時(shí)，則不放 
    {
        cout<<"能放不放"<<endl;
        b[s]=0;
        beibao(w,s+1,e,a,b);
    }
    
    if((w-a[s])<0)//a[s]放不進(jìn)去時(shí)，則不放 
    {
        b[s]=0;
        beibao(w,s+1,e,a,b);
    }    
} 

5、結(jié)果展示：

結(jié)果1.png

6、問(wèn)題總結(jié)：

• 1、sizeof(a)/sizeof(a[0])在數(shù)組傳入子函數(shù)時(shí)會(huì)出現(xiàn)問(wèn)題，上面代碼中test就是測(cè)試該代碼時(shí)的打印結(jié)果，在主程序中打印是3，沒(méi)有問(wèn)題；在子程序中打印是2，變小了。
• 2、遞歸程序的難點(diǎn)是我們沒(méi)法清晰的在大腦中想象程序執(zhí)行流程，這個(gè)時(shí)候邏輯就顯得非常重要了。

7、第二代代碼：

/*
《0/1背包問(wèn)題》
1、背包的重量被限制w
2、有一些物品，每個(gè)物品都有不同的重量
3、對(duì)于每個(gè)物品來(lái)說(shuō)，如果能裝進(jìn)去，可以選擇裝（1），
也可以選擇不裝（0）。 

修改意見(jiàn)：能不麻煩計(jì)算機(jī)的就自己解決。 
*/

#include<iostream>

using namespace std;

int beibao(int w,int s,int e,int n,int a[],int b[]); 

int main()
{
   int A[]={10,20,30};
   int B[]={0,0,0};
   
   beibao(50,0,2,3,A,B);
   
   return 0;
}

//打印所有可能的0/1背包問(wèn)題
int beibao(int w,int s,int e,int n,int a[],int b[]){    
    
    if(s>e){
        cout<<"{";
        for(int i=0; i<n; i++){
            if(b[i]==1){
                cout<<a[i]<<",";
            }
            else{
                cout<<0<<",";
            }
        }
        cout<<"}"; 
        cout<<""<<endl;
        return 0;
    }
    
    if((w-a[s])>=0)//a[s]可以放進(jìn)去時(shí)，則放 
    {
        b[s]=1;
        beibao(w-a[s],s+1,e,n,a,b);
    }
    
    if((w-a[s])>=0)//a[s]可以放進(jìn)去時(shí)，則不放 
    {
        b[s]=0;
        beibao(w,s+1,e,n,a,b);
    }
    
    if((w-a[s])<0)//a[s]放不進(jìn)去時(shí)，則不放 
    {
        b[s]=0;
        beibao(w,s+1,e,n,a,b);
    }    
} 

8、結(jié)果展示：

結(jié)果2.png

9、總結(jié)：

• 在遞歸程序中，邏輯是最重要的！

• 有時(shí)候大的問(wèn)題可以用小問(wèn)題分析
  小問(wèn)題.png
  
  
  算法核心.png