0
かなり単純なサブ問題に遭遇したときに問題を解決していました。 2つの文字列S1とS2が与えられた場合、merge(S1,S2)は、2つの文字列S1とS2を散在させることによって得られた文字列を表し、両方の文字の順序を維持して結果の文字列が辞書編集的に最小です。今2つの文字列をマージして、辞書的に最も小さなマージされた文字列を生成します。
例
S1 = abad
S2 = bbde
merge(S1, S2) = ababbdde
、私は、文字列の両方の最初の要素から開始貪欲法を適用した後、最小の要素を探し、その結果にそれを追加することによって問題を解決しようとしました。しかし、すぐに、これは常に最適な解決策につながるわけではないことが分かった。コードは以下のようになりました。
int n = a.size(), m = b.size();
int i =0, j=0, k=0; char array[n+m];
for(; i< n && j<n;) {
if(a[i] < b[j]) {
array[k] = a[i];
++i;
}
else {
array[k] = b[j];
++j;
}
++k;
}
while(i<n) {
array[k] = a[i];
++i;
++k;
}
while(j<m) {
array[k] = b[j];
++j;
++k;
}
for (int i = 0; i < n+m; ++i) {
cout<<array[i];
}
cout<<endl;
私はそれを後方に移動し、最大の文字を選択して後方から追加することを考えました。限られたテストで私はこれをうまくいきました。
int n = a.size(), m = b.size();
int i =n-1, j=m-1, k=n+m-1; char array[n+m];
for(; i>=0 && j>=0;) {
if(a[i] > b[j]) {
array[k] = a[i];
--i;
}
else {
array[k] = b[j];
--j;
}
--k;
}
while(i>=0) {
array[k] = a[i];
--i;
--k;
}
while(j>=0) {
array[k] = b[j];
--j;
--k;
}
for (int i = 0; i < n + m; ++i) {
cout<<array[i];
}
cout<<endl;
しかし、常に最適な解決策が常に得られるかどうかは不明です。
この解決法は最初のところ正しいですか？はいの場合、誰かが私に、これがいつも最適な解決策を作り出すのかについて私に少し証拠を与えることができます。
私はあなたの貪欲アルゴリズムは、ほぼ正しい感覚を持っていて、両方の文字列で同じ文字を見たとき、あなたの検索をfork場合には、作業を開始する必要があります。 – Manvel