1、环境配置：

• 系统：win10
• 编程语言：C++
• 编译器：DevC++

2、问题描述：

• 简单的0/1背包问题：设一背包可容纳物品的最大质量为m，现有n件物品，质量为m1，m2，...，mn，mi，均为正数，要从n件物品中挑选若干件，使放入背包的质量之和不超过m。

3、算法思想：

思想：对于一个物品来说，如果可以放到背包里，则有两种选择，一种是放，一种是不放。如果放不进去，则不放，继续下一个。
实现：用打印的方式打印出所有可能

分析.png

4、第一代代码：

/*
《0/1背包问题》
1、背包的重量被限制w
2、有一些物品，每个物品都有不同的重量
3、对于每个物品来说，如果能装进去，可以选择装（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背包问题
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]可以放进去时，则放 
    {
        cout<<"能放则放"<<endl; 
        b[s]=1;
        beibao(w-a[s],s+1,e,a,b);
    }
    
    if((w-a[s])>=0)//a[s]可以放进去时，则不放 
    {
        cout<<"能放不放"<<endl;
        b[s]=0;
        beibao(w,s+1,e,a,b);
    }
    
    if((w-a[s])<0)//a[s]放不进去时，则不放 
    {
        b[s]=0;
        beibao(w,s+1,e,a,b);
    }    
} 

5、结果展示：

结果1.png

6、问题总结：

• 1、sizeof(a)/sizeof(a[0])在数组传入子函数时会出现问题，上面代码中test就是测试该代码时的打印结果，在主程序中打印是3，没有问题；在子程序中打印是2，变小了。
• 2、递归程序的难点是我们没法清晰的在大脑中想象程序执行流程，这个时候逻辑就显得非常重要了。

7、第二代代码：

/*
《0/1背包问题》
1、背包的重量被限制w
2、有一些物品，每个物品都有不同的重量
3、对于每个物品来说，如果能装进去，可以选择装（1），
也可以选择不装（0）。 

修改意见：能不麻烦计算机的就自己解决。 
*/

#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背包问题
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]可以放进去时，则放 
    {
        b[s]=1;
        beibao(w-a[s],s+1,e,n,a,b);
    }
    
    if((w-a[s])>=0)//a[s]可以放进去时，则不放 
    {
        b[s]=0;
        beibao(w,s+1,e,n,a,b);
    }
    
    if((w-a[s])<0)//a[s]放不进去时，则不放 
    {
        b[s]=0;
        beibao(w,s+1,e,n,a,b);
    }    
} 

8、结果展示：

结果2.png

9、总结：

• 在递归程序中，逻辑是最重要的！
• 有时候大的问题可以用小问题分析 小问题.png
  算法核心.png