0-1背包问题

从数列中随意取几个数,使其和等于m,将其中所有的可能组合列出来

题目：输入两个整数m，n，从数列1,2,...,n中随意取几个数，使其和等于m，要求将其中所有的可能的组合列出，编程求解。

分析：0-1背包问题。首先定义一个bool型数组flag【n】，如果n被选中，则它相应的标志flag【n-1】=true。

（1）如果m

（2）如果m>n*(n+1)/2，则m过大，直接返回。

（3）如果m在【n,n*(n+1)/2】之间，则将n的标志flag[n-1]=true，然后令m=m-n, n=n-1递归调用func(m，n)。

（4）如果m==0，则输出结果

代码如下：

bool *flag;
int total=0;
void func(int m,int n)
{
   if(m>n*(n+1)/2)
    return;
   if (0==m)
   {
    for (int i=0;i     {
     if (flag[i])
     {
      cout<      }
    }
    cout<    }
   else
   {
    if (m     func(m,m);
    else
    {
     flag[n-1]=true;
     func(m-n,n-1);
      flag[n-1]=false;///返回后将n的标志置零，
                                      //从func(m,n-1)开始，重新计算
     func(m,n-1);
    }
   }
}

void main()
{
 int m,n;
 cout<<"Put in m ,n"<  cin>>m>>n;
 flag=new bool[n];
 for (int i=0;i  {
  flag[i]=false;
 }
 total=n;
   
   func(m,n);

   delete[] flag;

}

 

//////////////////////////////////////////

#include 

#include 

using namespace std; 

 

void findNums(int n,int leftSum,deque<int>& deq) 

{ 

       if(n<0||leftSum<0)return;    //已经遍历完数列，返回 

       if(leftSum>0) 

       { 

           deq.push_front(n);              //将n加入数列或者不加入 

           findNums(n-1,leftSum-n,deq); 

           deq.pop_front(); 

           findNums(n-1,leftSum,deq); 

       } 

       else {                      //当前数列综合已经达到要求，则输出 

           deque<int>::iterator i=deq.begin(); 

           for(;i!=deq.end();++i) 

           { 

               cout<<*i<<" "; 

           } 

           cout<

       } 

} 

 

int main() 

{ 

    deque<int> myDeq; 

    findNums(10,35,myDeq); 

    return 0; 

}