JavaScriptを用いた購入システムの券枚数決定のアルゴリズムについて

Question

お世話になっております。

今回、券の購入システムの構築を勉強のため行っております。
方法の概要として
最小の購入金額<オッズによる払い戻しになるよう各券の購入枚数を求める計算式になっています。

具体的な方法は以下の通りです。

購入する券を配列に起こす(ary)。
↓
haraiGenHairetuにオッズのみの配列を作成、bakenMaisuにはこれから購入して行く券の枚数を指定する配列(初期値は全て1枚とします)を準備
↓
オッズ×馬券枚数を算出し、kakezan配列に代入
↓
kakezan配列の最小値を求め、haraiGenHairetuMinに代入
↓
bakenMaisuの合計を求める①
↓
haraiGenHairetuMinの値があるharaiGenHairetuのインデックス番号をharaiGenIndexに代入
↓
bakenMaisuのharaiGenIndex番目に+1をする(購入する馬券が一枚増える)
↓
bakenMaisu[haraiGenIndex]=haraiGenBakenMaisu
↓
もしbakenMaisu>haraiGenHairetuMinならば、①に戻る

正解としてはbakenMaisu[2,44,1,6,2,1,3,2,1,1,1,5,2,19,2,8,1]が最小購入金額ですが、この方法だと[2, 47, 1, 6, 2, 1, 3, 2, 1, 1, 1, 5, 2, 20, 3, 9, 1]が最終解となり若干差が生じます。

この差に付いては何が問題なのでしょうか。
また、より処理速度を上げるにはどういった点を修正する必要性があるでしょうか。

よろしくお願いいたします。

<script src="decimal.min.js"></script>
		<script>
			var ary =　[
				["2", 72.6], 
				["4", 2.3],
				["5", 151.8], 
				["6", 18],
				["7", 66.8],
				["1-2", 347.2], 
				["1-3", 37.4],
				["1-4", 54],
				["1-5", 662.7], 
				["1-6", 169.6],
				["1-7", 607.5],
				["3-1", 23], 
				["3-2", 86.8], 
				["3-4", 5.4],
				["3-5", 50.7], 
				["3-6", 13],
				["3-7", 177.8],
				
			];
			
			var haraiGenHairetu = [];
			var bakenMaisu = [];
			var garaiKakeBakenMaisu = [];
			for(var i=0;i<ary.length;i++){
					var haraiGen=ary[i][1];
					haraiGenHairetu.push(haraiGen);
					bakenMaisu.push(1);	
			}
			function kakeruGoukei(){
					for(var i=0;i<ary.length;i++){
						var kakezan = new Decimal(haraiGenHairetu[i]).times(bakenMaisu[i]).toNumber();
						garaiKakeBakenMaisu.push(kakezan);
					}
					var haraiGenHairetuMin = Math.min.apply(null,haraiGenHairetu);

					var sum  = function(bakenMaisu) {
						var sum = 0;
						bakenMaisu.forEach(function(elm) {
							sum += elm;
						});
						return sum;
					};

					var haraiGenIndex = haraiGenHairetu.indexOf(haraiGenHairetuMin);
                    var haraiGenBakenMaisu=bakenMaisu[haraiGenIndex]+1;
                    bakenMaisu[haraiGenIndex]=haraiGenBakenMaisu;

					while(sum(bakenMaisu)>haraiGenHairetuMin){
						console.log(bakenMaisu);
						var sum  = function(bakenMaisu) {
                            var sum = 0;
                            bakenMaisu.forEach(function(elm) {
                                sum += elm;
                            });
                            return sum;
                        };

						garaiKakeBakenMaisu.splice(0, ary.length);
						for(var i=0;i<ary.length;i++){
							var kakezan = new Decimal(haraiGenHairetu[i]).times(bakenMaisu[i]).toNumber();
                            garaiKakeBakenMaisu.push(kakezan);
                        }
						var haraiGenHairetuMin = Math.min.apply(null,garaiKakeBakenMaisu);
						
						var haraiGenIndex = garaiKakeBakenMaisu.indexOf(haraiGenHairetuMin);
						var haraiGenBakenMaisu=bakenMaisu[haraiGenIndex]+1;
						bakenMaisu[haraiGenIndex]=haraiGenBakenMaisu;
						
					}
				
				document.write("購入合計金額は"+sum(bakenMaisu)*100+"です。<br/>");
				var saisyou =(sum(bakenMaisu)*100)-(haraiGenHairetuMin*100);
				document.write("最小収益は"+saisyou+"です。");
				var haraiGenHairetuMax = Math.max.apply(null,garaiKakeBakenMaisu);
				var saidai =((haraiGenHairetuMax*100)-sum(bakenMaisu)*100);
				document.write("最大収益は"+saidai+"です。");
							   
					
			}
			
			kakeruGoukei();

Comments

[Orlofsky]

> var ary =　[
= の次に全角の空白が入っています。直されては？

Answer 1

while(sum(bakenMaisu)>haraiGenHairetuMin){

↑の部分ですが、bakenMaisuがkuroishiさんが考える正解[2,44,1,6,2,1,3,2,1,1,1,5,2,19,2,8,1];の時、

sum(bakenMaisu) // = 101
haraiGenHairetuMin // = 98.9

なので、ループを抜けません。

なぜならば、その時点でのharaiGenHairetuMinは直前のループで計算されたものなので、馬券枚数に+1する前の値である、[2,43,1,6,2,1,3,2,1,1,1,5,2,19,2,8,1];に基づいて計算された結果だからです。

なので、問題は「bakenMaisuを変更したときにharaiGenHairetuMinを再計算していないから」です。

---

また、速度向上については、spliceやpushが遅いような気がしましたが、実際に試してはいません。

Comments

[kuroishi]

ありがとうございました！質問の意図も汲み取っていただき、感謝しております。