スーパーのマルエツのキャンペーンでは、レシート３０００円で１口応募できる。（レシート合算可） https://www.ichance.jp/cp/maruetsu-dreamwinter/
たとえば
以下のレシートがあった場合は
- 600
- 1000
- 2000
- 2500
以下のようにまとめることで「２口応募」できる。
- 1口目 600, 2500
- 2口目 1000, 2000
以下のレシートがあった場合はどうだろう。
- 1676
- 843
- 1000
- 233
- 1731
- 321
- 179
- 259
- 460
- 1594
- 3544
- 632
- 2172
- 2623
- 1102
- 84
- 466
- 306
- 855
- 3255
- 1609
- 1345
- 1170
- 4220
- 6231
- 180
- 91
- 2937
- 544
- 1577
- 421
- 3899
- 585
- 671
- 1811
- 875
- 384
- 950
- 1618
これは、パッとわからない。
パッとわからないので、テキトーに組み合わせて出来た結果が「１０口」だとする。
もうすこし組み合わせを頑張れば「１１口」や「１２口」になったりするかもしれない。
しかし、テキトーに手作業だとだいぶ疲れるし、無意味なような気がするので、以下のアルゴリズムを考えた。
計算1
- レシートから１枚ランダムに選んで、テーブルに置く
- テーブルの上にあるレシートを見る
- レシートの合計が3000円以上なら、コップを用意してそこにテーブルの上のレシートを入れる。1. を実行する
- レシートの合計が3000円未満なら、1. を実行する
- と 2. をレシートを取り尽くすまで実行する。
- レシートを取り尽くしたら、出来たコップ（3000円以上のレシートが入ったコップ）の数を記録する
計算1をN回繰り返し、出来たコップの数の記録を見る。
最も多い「コップの数」が、乱択の結果、確率的に分かった応募できる最大の口数。（＝必ずしも正解とは言えない）
上のコードを swift で書いた。（Nは100万回）
import Foundation let passValue: Int = 3000 // 基準値 let tryMax: Int = 1000000 // 試行回数 // 入力 let inputValues: [Int] = [ 1676, 843, 1000, 233, 1731, 321, 179, 259, 460, 1594, 3544, 632, 2172, 2623, 1102, 84, 466, 306, 855, 3255, 1609, 1345, 1170, 4220, 6231, 180, 91, 2937, 544, 1577, 421, 3899, 585, 671, 1811, 875, 384, 950, 1618 ] // あらかじめ基準値以上のグループを作成する var passedGroups: [[Int]] = [] // すでに基準値以上のグループ var inputValues2: [Int] = [] for value in inputValues { if value >= passValue { passedGroups.append([value]) continue } inputValues2.append(value) } var groupNumMap: [Int: Int] = [:] // グループ数の出現頻度のマップ var bestGroups: [[Int]] = [] // 最適なグループ配列 var lastPercent: Int = 0 // print("- count \(inputValues2.count)") // print("- sum \(inputValues2.reduce(0, +))") // print("") // ランダムに基準値を超えるグループを作成する for i in 0..<tryMax { // 一時変数を準備する var tempGroups: [[Int]] = [] // 一時的なグループの配列 var tempValues: [Int] = inputValues2 // 一時的な値の配列 var tempGroup: [Int] = [] // 一時的なグループ // ランダムに基準値以上のグループの配列を作成する while true { // ランダムなインデックスを得る let index: Int = Int.random(in: 0..<tempValues.count) let value: Int = tempValues[index] tempValues.remove(at: index) // 一時的なグループに値を追加する tempGroup.append(value) let reduceValue: Int = tempGroup.reduce(0, +) if reduceValue >= passValue { // 一時的なグループの合計が基準値以上の場合 // -> グループを、一時的なグループ配列に追加する tempGroups.append(tempGroup) tempGroup = [] // 一時的なグループをクリア } if tempValues.count > 0 { continue } // 値がなくなったので試行終了 break } // グループ数の出現カウントを控える let groupsCount: Int = tempGroups.count + passedGroups.count groupNumMap[groupsCount] = (groupNumMap[groupsCount] ?? 0) + 1 if tempGroups.count > bestGroups.count { // 最適なグループ数を超えたら、最適なグループを更新する bestGroups = tempGroups } let percent: Int = Int((Float(i) / Float(tryMax)) * 100) if percent > lastPercent { lastPercent = percent print("\(percent)%") } } // 計算の結果得た最適なグループ配列に、あらかじめ作成したすでに基準値以上のグループを合成する bestGroups.insert(contentsOf: passedGroups, at: 0) print("\n\n") // 結果を出力 print("# Result\n") // 最適なグループ配列を出力 print("## Best groups") print("group numbers : \(bestGroups.count)") print("") for i in 0..<bestGroups.count { print("### Group\(i + 1)") for j in 0..<bestGroups[i].count { print("- \(bestGroups[i][j])") } print("") } // グループ数の出現頻度 print("## Frequency of group numbers\n") let sortedKeys: [Int] = groupNumMap.keys.sorted() for key in sortedKeys { print("### \(key)") print("- count \(groupNumMap[key] ?? 0)") let percent: Float = (Float(groupNumMap[key] ?? 0) / Float(tryMax)) * 100 print("- percent \(percent)%") }
これを実行すると、結果の出力は以下。
１５口応募できるようだ。
全体のうち、口数の出現頻度が
- 12口が 0.7%
- 13口が 45%
- 14口が 52%
- 15口が 1%
となる。
# Result ## Best groups group numbers : 15 ### Group1 - 3544 ### Group2 - 3255 ### Group3 - 4220 ### Group4 - 6231 ### Group5 - 3899 ### Group6 - 2623 - 1102 ### Group7 - 306 - 855 - 259 - 1609 ### Group8 - 233 - 1594 - 544 - 180 - 632 ### Group9 - 1676 - 1345 ### Group10 - 466 - 2937 ### Group11 - 950 - 460 - 321 - 1731 ### Group12 - 1577 - 1000 - 585 ### Group13 - 84 - 1170 - 2172 ### Group14 - 91 - 1618 - 384 - 671 - 843 ### Group15 - 179 - 1811 - 421 - 875 ## Frequency of group numbers ### 12 - count 7584 - percent 0.7584% ### 13 - count 453582 - percent 45.3582% ### 14 - count 528201 - percent 52.8201% ### 15 - count 10633 - percent 1.0633%
