複数の値から、合計が1000以上になるような組み合わせを複数作成するロジック

Question

前提・実現したいこと

個人的に作成しようと思っているプログラムで以下のようなロジックを考えていますが、あまりいい方法が思いつきません。
皆様のお力をお借りできればと思い質問いたしました。

複数の値から、合計が1000以上になるような組み合わせを複数作成する。
出来る限り1000に近い組み合わせを出来る限り多く作成できる組み合わせを作成する。

ここに質問の内容を詳しく書いてください。
例えば以下の数字が与えられたときに、結果のような値を出力するプログラムを書きたいと思っています。
【与えられた数字】
211,543,1200,365,911,89,21,460,799

【結果】
1200(1200)
911,89(1000)
543,460(1003)
799,211(1010)
あまり
365,21

以下私の考えたロジックです。
1000を超える全組み合わせを探索したのち、
そこから「与えられた数字」が被らない組み合わせを全パターン探索する。
その後、そのパターンの中から「与えられた数字」を多く使っているものを選択する。

ただ、あまりにも計算量も多く、きれいなロジックではないと思っています。
またこの方法では出来るだけ1000に近い数字を出すというロジックにはならないのではないかと思っています。

もしいい方法があればご教授のほどよろしくお願いいたします。

Comments

[退会済みユーザー]

3点確認させてください。1) 200+300+500など、3個以上の数字を組み合わせて1000以上にするケースを想定する必要はありますか? 2) [150, 200, 850, 900]のような数字があった場合、1050(150+900), 1050(200+850)と1000(150+850), 1100(200+900)ではどちらが望ましい答えですか? 3) 与えられる数字は何個くらいまでを想定していますか?

[y_y_y]

ご質問ありがとうございます。
1)3つ以上の組み合わせも想定しております。
2)確かにこのパターンだと困りますね…
合計金額が同じで、かつ使用している数字の数も同じなので内部的には特に優劣ありませんが、
付けたほうがロジックを組みやすいようでしたら1000により近い組み合わせがある方の1000(150+850), 1100(200+900)が望ましい答えだとしてください。
3)10~100くらいを想定しています。

[m.ts10806]

>個人的に作成しようと思っているプログラムで
想定する言語があるのでしたらタグに追加しておくとその言語にそったアドバイスも得やすくなるかもしれません。

[y_y_y]

ありがとうございます。
これから作成しようと思っていたのでまだ言語を決めていなかったのですが、書きなれているのでpythonにしました。
タグにも追加しました。

Answer 1

数字の数が100個程度であれば、力技で十分ではないでしょうか。
私の考えたロジックは以下の通りです。

1. 与えられた候補の数字を使用して1,000以上となるベストな組み合わせを選ぶ
2. 前ステップで選んだ数字を候補から取り除く
3. 最初のステップに戻る

ベストな組み合わせは以下の基準で選択

• できるだけ1,000に近いこと
• 使用している数値の数が少ないこと
• 使用している数値の最小値ができるだけ小さいこと

数字100個でpythonで書いても1,2秒で処理できるので、c++とかで書けば一瞬で終わると思います。

from random import randint, seed

def total_to(numbers, target=1000):
    """
    numbersの中の数字をいくつか組み合わせてtarget以上になる組み合わせのうちベストな組み合わせを返す
    ベストの基準: targetに近いこと、使用している数字の数が少ないこと、より小さい数字を使用していること
    該当無しの場合はNoneを返す
    """
    if sum(numbers) < target:
        return None
    res = []
    status = {0: (0, [])}
    for n in numbers:
        u = dict()
        for k, v in status.items():
            if k + n >= target:
                res.append((k+n, len(v[1])+1, sorted(v[1]+[n])))
            elif k+n not in status or status[k+n] > (v[0]+1, v[1]+[n]):
                u[k+n] = (v[0]+1, sorted(v[1]+[n]))
        status.update(u)
    return sorted(res)[0][2]


#numbers = [211, 543, 1200, 365, 911, 89, 21, 460, 799]
seed(3) # 乱数の固定用
numbers = [randint(10, 1100) for _ in range(100)] # 10～1100の乱数を100個生成
print(numbers)

while True:
    picks = total_to(numbers)
    if picks:
        print(f'{picks}, ({sum(picks)})')
        for p in picks:
            numbers.remove(p)
    else:
        print(f'残り:{numbers}')
        break

実行結果のイメージ

[497, 277, 767, 980, 144, 36, 970, 541, 489, 402, 973, 985, 823, 318, 484, 320,
1081, 808, 41, 141, 336, 97, 626, 73, 561, 978, 803, 884, 818, 920, 284, 758, 20
9, 83, 288, 1023, 454, 538, 903, 626, 872, 1048, 800, 728, 844, 485, 699, 68, 58
2, 344, 678, 223, 442, 556, 593, 264, 139, 997, 1000, 191, 714, 146, 850, 318, 5
1, 611, 884, 860, 253, 100, 102, 783, 687, 581, 1045, 493, 83, 644, 24, 167, 231
, 74, 414, 845, 607, 549, 329, 96, 705, 652, 747, 293, 783, 781, 952, 1075, 800,
 220, 1048, 565]

[1000], (1000)
[97, 903], (1000)
[253, 747], (1000)
[24, 209, 767], (1000)
[36, 141, 823], (1000)
[41, 231, 728], (1000)
[51, 191, 758], (1000)
[68, 288, 644], (1000)
[73, 83, 844], (1000)
[74, 344, 582], (1000)
[83, 336, 581], (1000)
[100, 293, 607], (1000)
[102, 220, 678], (1000)
[139, 320, 541], (1000)
[144, 318, 538], (1000)
[146, 167, 687], (1000)
[223, 284, 493], (1000)
[442, 561], (1003)
[454, 549], (1003)
[414, 593], (1007)
[96, 264, 318, 329], (1007)
[402, 611], (1013)
[1023], (1023)
[484, 556], (1040)
[1045], (1045)
[1048], (1048)
[1048], (1048)
[485, 565], (1050)
[277, 781], (1058)
[1075], (1075)
[1081], (1081)
[489, 626], (1115)
[497, 626], (1123)
[652, 699], (1351)
[705, 714], (1419)
[783, 783], (1566)
[800, 800], (1600)
[803, 808], (1611)
[818, 845], (1663)
[850, 860], (1710)
[872, 884], (1756)
[884, 920], (1804)
[952, 970], (1922)
[973, 978], (1951)
[980, 985], (1965)
残り:[997], (997)

Comments

[y_y_y]

返信が遅くなり申し訳ありません。
やりたかったことにかなり近い回答です。
ありがとうございます。参考にさせていただきます。