c++遡及法による作業配分問題の実現
6176 ワード
構想
まず1つの配列を初期化して1~nを格納する.選択
1:遡及する境界条件現在の層数が実際の需要層数より大きくなる
2:現在のレイヤ数が以下の実際のレイヤ数より小さい場合
再帰に入る
再帰的な内容:
1:現在のレイヤでループを使用し、ループの開始点iを現在のレイヤとし、最終レイヤ数に重点を置く
{サイクル内
まずx中の第x〔i〕とx〔現在の層〕を交換する.
すなわち、x〔t〕層が選択されている.
その後、x〔現在のレイヤ〕〔x〔現在のレイヤ〕〕を追加します.
再帰(層数+1);
再帰が完了したら、上ノードに戻ります.
コストから現在のレイヤを減算します.
x〔t〕とx〔i〕を再交換する.
}
まず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;
}
,