動的計画法で部分和問題を解くときどの数字が使われているか知りたい

Question

動的計画法で部分和問題を解くときどの数字が使われているか知りたいです。あまり知識がないのでこのコードからlistのどの数字が使われたかを判断するにはどのように変更すればいいでしょうか？

def mins(a, A):
    # 初期化
    N = len(a)
    inf = float("inf")
    dp = [[inf for i in range(A + 1)] for j in range(N + 1)]
    dp[0][0] = 0

    # DP
    seki = []
    for i in range(N):
        for j in range(A + 1):
            if a[i] <= j:  # i+1番目の数字a[i]を足せるかも
                l = min(dp[i][j - a[i]] + 1, dp[i][j])
                dp[i + 1][j] = l
            else:  # 入る可能性はない
                dp[i + 1][j] = dp[i][j]

    return dp[N][A]
 
list = [4,8,6]
print(mins(list,10))

Answer 1

情報提供のみ。
動的計画法で求めた解を全列挙する方法にて、部分和問題をDPで解き、さらにそのDPから解を復元する方法について記載されています。
ちゃんと読めていませんが、図解で説明されていますので理解できればご自身のコードに組み込めるかもしれません。
さらに各種の問題の解法として意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法も参考になるかもしれませんが「部分和問題」ズバリの例は記載ありません。

Answer 2

aの要素がどのタイミングで使われているのかみたいということであれば

a[i]の値が使われるのがここなので、

l = min(dp[i][j - a[i]] + 1, dp[i][j])

ここの前か後で適当に見たい値をprintすればよいです

---

条件を満たす値の組を求める必要がある場合には

1組でよければ復元テーブルというものを用意する(ググれば詳しい解説がいくらでもでてきます)
全列挙する必要があるならdpを逆からたどってdp[0][0]にたどり着ける組を探します。

Comments

[hiei1]

listのどの数を使うと正解になるかを表示するのは不可能ですか
例えば　[4,8,6]、１０の場合
４　６　数は２みたいな

[ozwk]

まずもともとの問題はなんですか?

[hiei1]

4, 6, 8の3枚のカードがある。

この3枚のカードから何枚か選んで、合計を10にすることができるだろうか。

10にできるのであれば カードの値と枚数を表示してくださいです

[ozwk]

「知りたい」というからてっきりデバッグ目的とか興味かと思っていたら普通に問題の要件なんですね。

複数の組み合わせがある場合はどうするのですか?

[hiei1]

それは考えないらしいです。なぜかわかりませんが

[ozwk]

とりあえず追記しました