回溯法

    技术2022-05-17  45

    N个鸡蛋分到M个篮子里(N>M),不能有空篮子,对于任意不大于于N的数,保证有几个篮子的鸡蛋数和等于此数,编程实现输入N,M两个数,输出所有鸡蛋的方法

     

    全输出的话本质就是搜索+剪枝。

    (n,m,min)表示当前状态,按照篮子里蛋的数目从小到大搜索。搜到了第m个篮子,1..m个篮子面共放了n个蛋,当前的篮子放了min个蛋。下一个扩展(n+t,m+1,t),for t=min...n+1。当n+(M-m)*min>N (鸡蛋不够时)或者2^(M-m)*n+2^(M-m)-1<N(鸡蛋太多)时 把这个枝剪掉……  ; 

    太多时的情况如下: n,n+1,2n+2,4n+4,8n+8....

    #include <iostream> using namespace std; long pow2[20]; int N,M; int ans[1000]; void solve( int n , int m , int Min ) { if(n == N && m == M) { for(int i=1;i<=M;i++) { cout<<ans[i]<<" "; } cout<<endl; return ; } else if( n + (M-m)*Min > N || N > pow2[M-m]*n + pow2[M-m]-1) return ; else { for(int i = Min; i <= n+1; i++) { ans[m+1] = i; solve(n+i,m+1,i); } } } int main() { pow2[0] = 1; for(int i=1;i<20;i++) { pow2[i] = pow2[i-1]<<1; } cin>>N>>M; if( M > N || pow2[M]-1 < N) { cout<<"没有这样的组合"<<endl; } solve( 0 , 0 , 1 ); system("pause"); return 0; }


    最新回复(0)