- ベストアンサー
数値を複数の群に分ける最適な組み合わせを求める方法
- 数値を複数の群に分ける方法について説明します。与えられた数値列で隣り合う数値しか同じ群に含めることはできず、各群の合計値が最も均等になる組み合わせを求めることが目標です。
- 例えば、数値列{5,2,7,12,6,15,4}を3つの群に分ける場合、{5,2,7},{12},{6,15,4}という組み合わせが最も均等です。
- 実際の問題では、組み合わせの数が増えると計算時間に影響するため、全ての組み合わせを試さずに最適な組み合わせを求める方法を提示してください。
- みんなの回答 （92）
- 専門家の回答
質問者が選んだベストアンサー
>回答No.23 amanojaku1 「2018/06/15 03:48:47」の時点で修正しました。 それ以前にコピーしている場合は注意して下さい。 数値を複数の群に分ける最適な組み合わせを求める方法 http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&
その他の回答 (91)
- amanojaku1
- ベストアンサー率54% (265/488)
>for(let k = 0; k<(gmq.length-1); k++){ >gmq[k]++; >for(let i = 0; i<k; i++){ >gmq[i] = 1; >} >gmq[gmq.length-1] = gpa.length >document.write( >'k='+k+'; '+ >'gmq[k]='+gmq[k]+'; '+ >'<br>'); >// p = 0; >for(let i = 0; i<(gmq.length-1); i++){ >gmq[gmq.length-1] -= gmq[i]; >// p += gmq[i]; >// gmp[i+1] = p; >} >document.write('>gmq='+gmq+'<br>'); >if(0<gmq[gmq.length-1]){ >break; >} >} (分岐予測が外れたら(CPUの)パイプラインのStall(ストール：停止状態)が発生しますので)内部的な条件付分枝は減らすべきですね。 k = 0; gmq[gmq.length-1] = 0; while(gmq[gmq.length-1]<=0 && k<(gmq.length-1)){ gmq[k]++; for(let i = 0; i<k; i++){ gmq[i] = 1; } gmq[gmq.length-1] = gpa.length document.write( 'k='+k+'; '+ 'gmq[k]='+gmq[k]+'; '+ '<br>'); // p = 0; for(let i = 0; i<(gmq.length-1); i++){ gmq[gmq.length-1] -= gmq[i]; // p += gmq[i]; // gmp[i+1] = p; } document.write('>gmq='+gmq+'<br>'); k++; }
- amanojaku1
- ベストアンサー率54% (265/488)
>最大値最小値を条件付分岐なしに記述できると良いのですが。 「std::min、std::max」の内部はアセンブラなので、その可能性があるかもしれないので、試してみて下さい。
- amanojaku1
- ベストアンサー率54% (265/488)
>下記を記述してみてコンパイルが通るか試してみては？ > >#pragma forceinline std::min >#pragma forceinline std::max 良く分かりませんが、例では行末のセミコロンは付いてないようです。
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.58 amanojaku1 >VisualC++では出来ないと思います。 下記を記述してみてコンパイルが通るか試してみては？ #pragma forceinline std::min #pragma forceinline std::max
- amanojaku1
- ベストアンサー率54% (265/488)
>「#pragma forceinline」で定義すると関数をinline化できるみたいな記事がありましたので。 下記は「#pragma inline」の例です。 top＞コンパイラ編＞コンパイラ言語仕様＞拡張言語仕様＞拡張言語仕様の使用方法＞関数のインライン展開（#pragma inline/#pragma noinline） http://tool-support.renesas.com/autoupdate/support/onlinehelp/ja-JP/csp/V4.01.00/CS+.chm/Compiler-CCRL.chm/Output/cd_EXP_LANG16.html >#pragma inline i_func > >static int i_func(int i) >{ > return ++i; >}
お礼
これは特定のコンパイラでしか使えないpragmaですね。そもそもpragmaは言語仕様ではなく、コンパイラ固有のオプションのようなものですね。 私の環境ではこのpragmaは使えませんでした。
- amanojaku1
- ベストアンサー率54% (265/488)
>min_element,max_elementはSTLのライブラリ関数なのでinline化は出来ません。 >他の環境なら可能かも知れませんが、VisualC++では出来ないと思います。 「min_element,max_element」(はプープが入るので)ではなく「std::min、std::max」のほうです。 「#pragma forceinline」で定義すると関数をinline化できるみたいな記事がありましたので。 >関数呼び出しではなく最大値最小値を求めるロジックを直接whileループ中に書きました。つまり普通にinlineになっています。 分岐予測が外れたら(CPUの)パイプラインのStall(ストール：停止状態)が発生します。 最大値最小値を条件付分岐なしに記述できると良いのですが。
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.54 amanojaku1 >if((gmc+1)<gmp.length){ >if(pn==i){ >document.write(' | '); >gmc++; >pn += gmq[gmc]; >} >} (分岐予測が外れたら(CPUの)パイプラインのStall(ストール：停止状態)が発生しますので)内部的な条件付Jumpは減らすべきですね。 if((gmc+1)<gmp.length && pn==i){ document.write(' | '); gmc++; pn += gmq[gmc]; }
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.54 amanojaku1 >とにかくwhileループ内がボトルネック つまり、それ以外は どうでも良い。
- amanojaku1
- ベストアンサー率54% (265/488)
>gmpは使用しない。 確かに良く考えたら無くても良いですね。 変な部分があったので修正しましたので一応 投稿します(とにかくwhileループ内がボトルネック)。 <head> <meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS"> <!-- charset=Shift-JIS、UTF-8 --> <TITLE>test</TITLE> </head> <body> <script type="text/javascript"> <!-- gpa = [5,2,7,12,6,15,4]; gp = 4; gmq = Array(gp).fill(1); gmp = Array(gp).fill(0); gmmin = -1; gmmax = -1; gmmdif = -1; gtmin = -1; gtmax = -1; gtmdif = -1; gppc = 0; gmq[gmq.length-1] = gpa.length for(let i = 0; i<(gmq.length-1); i++){ gmq[gmq.length-1] -= gmq[i]; } while(0<gmq[gmq.length-1]){ gppc++; gmt = Array(gp).fill(0); gmc = 0; pn = gmq[0]; for(let i = 0; i<gpa.length; i++){ if((gmc+1)<gmp.length){ if(pn==i){ document.write(' | '); gmc++; pn += gmq[gmc]; } } gmt[gmc] = gmt[gmc]+gpa[i]; document.write(gpa[i]+','); } document.write('<br>'); document.write('>gmq='+gmq+'<br>'); document.write('gmt='+gmt+'<br>'); gmmin = gmt[0]; gmmax = gmt[0]; for(let m = 1; m<gmt.length; m++){ gmmin = Math.min(gmmin,gmt[m]); gmmax = Math.max(gmmax,gmt[m]); } gmmdif = gmmax-gmmin; document.write( 'gmmin='+gmmin+'; '+ 'gmmax='+gmmax+'; '+ 'gmmdif='+gmmdif+'; '+ '<br>'); if((gtmdif<0)||(gtmdif>gmmdif)){ gtmdif = gmmdif; gtmin = gmmin; gtmax = gmmax; gtmq = gmq.slice(); // gtmp = gmp.slice(); } document.write( 'gtmin='+gtmin+'; '+ 'gtmax='+gtmax+'; '+ 'gtmdif='+gtmdif+'; '+ '<br>'); document.write('<br>'); for(let k = 0; k<(gmq.length-1); k++){ gmq[k]++; for(let i = 0; i<k; i++){ gmq[i] = 1; } gmq[gmq.length-1] = gpa.length document.write( 'k='+k+'; '+ 'gmq[k]='+gmq[k]+'; '+ '<br>'); // p = 0; for(let i = 0; i<(gmq.length-1); i++){ gmq[gmq.length-1] -= gmq[i]; // p += gmq[i]; // gmp[i+1] = p; } document.write('>gmq='+gmq+'<br>'); if(0<gmq[gmq.length-1]){ break; } } document.write('<br>'); } document.write('<br>'); document.write("<< Answer >>"+'<br>'); document.write('PatternCounter='+gppc+'<br>'); // gmp = gtmp; gmq = gtmq; gmt = Array(gp).fill(0); gmc = 0; pn = gmq[0]; for(let i = 0; i<gpa.length; i++){ if((gmc+1)<gmp.length){ if(pn==i){ document.write(' | '); gmc++; pn += gmq[gmc]; } } gmt[gmc] = gmt[gmc]+gpa[i]; document.write(gpa[i]+','); } document.write('<br>'); document.write('>gmq='+gmq+'<br>'); document.write('gmt='+gmt+'<br>'); document.write( 'gtmin='+gtmin+'; '+ 'gtmax='+gtmax+'; '+ 'gtmdif='+gtmdif+'; '+ '<br>'); // --> </script> </body> </html>
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.46 amanojaku1 >この結果、2000万パターンで ちなみに、このように何千万回もループする場合、関数を呼ぶだけでも微妙に時間が かかるので、どうしても関数を呼ぶ必要が有る場合はインライン化してみて下さい。
お礼
コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。 それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。