部分和問題

Python sum combinations based on elements [on hold] – StackOverflow

これは部分和問題で以下(特に重複ありの方)と同じ.

配列要素の合計値がターゲット値になる様な組み合わせを全て求める

How can I list all of the ways to sum a list of numbers to N, with repeats, in python?

(汚いけど)上記のコードをそのまま使うと,

import numpy as np

a1 = [16, 17, 23, 24, 39, 40]
a2 = [100]

N = len(a1) - 1
elm = []
for i, step in enumerate(a1):
    temp = [1] * (N - i)
    elm.append(np.arange(0, 100, step).reshape(-1, *temp))

res = 0
for x in elm:
    res = res + x

for t in a2:
    print(np.argwhere(res == t))

[[2 4 0 0 0 0]]

16 x 2 + 17 x 4 = 100

と求まる事が分かる.

for t in a2:
    print('------'*30)
    print(f'target value: {t}')
    a = np.argwhere(res == t)
    if len(a) == 0:
        print('no matching')
    else:
        for x in a:
            if hasattr(x[0], '__iter__'):
                for e in x:
                    print(f'16: {e[0]}, 17: {e[1]}, 23: {e[2]}, 24: {e[3]}, 39: {e[4]}, 40:{e[5]}')
            else:
                print(f'16: {x[0]}, 17: {x[1]}, 23: {x[2]}, 24: {x[3]}, 39: {x[4]}, 40:{x[5]}')
    print('\n')

target value: 100
16: 2, 17: 4, 23: 0, 24: 0, 39: 0, 40:0

広告
カテゴリー: 未分類 パーマリンク

部分和問題 への1件のフィードバック

  1. ピンバック: 制約最適化問題の実現可能な領域を視覚化したい | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中