c++遡及法による作業配分問題の実現

6176 ワード

構想
まず1つの配列を初期化して1~nを格納する.選択
1:遡及する境界条件現在の層数が実際の需要層数より大きくなる
2:現在のレイヤ数が以下の実際のレイヤ数より小さい場合
再帰に入る
再帰的な内容:
1:現在のレイヤでループを使用し、ループの開始点iを現在のレイヤとし、最終レイヤ数に重点を置く
{サイクル内
まずx中の第x〔i〕とx〔現在の層〕を交換する.
すなわち、x〔t〕層が選択されている.
その後、x〔現在のレイヤ〕〔x〔現在のレイヤ〕〕を追加します.
再帰(層数+1);
再帰が完了したら、上ノードに戻ります.
コストから現在のレイヤを減算します.
x〔t〕とx〔i〕を再交換する.
#include 
 
  
using namespace std;
int x[100];
int n;//  
int ren[100][100];
int mini=100000;
int cost=0;
 
  
 
  
void Backgui(int t)
{ if(t>n)
    { if(cost 
  
            mini=cost;
//        for(int i=1;i<=n;i++)
//        {     cout< ";
//        }
//         cout<   ;
        return;}
 
  
     for(int i=t;i<=n;i++)
    {   swap(x[i],x[t]);
         cost+=ren[t][x[t]];
       Backgui(t+1);
       cost-=ren[t][x[t]];
       swap(x[i],x[t]);
 
  
 
  
 
  
     }
 
  
 
  
}
 
  
int main()
{  cin>>n;
    for(int i=1;i<100;i++)
    {    x[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {   cin>>ren[i][j];
        }
    }
    Backgui(1);
   cout< 
  
    return 0;
}