ナップザック問題で複数の経路が存在する場合

ナップザック問題で、たとえば、
n=4個の品物で、重さと価値が（w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
で、重さの総和W=5を超えないように選んだ時、価値の総和の最大値を求める問題で、答えは、
7（0, 1, 3番の品物を選ぶ）
7（0, 2番の品物を選ぶ）
の２通りありますが、価値の総和の最大値だけでなく、２分木を使って２分木ノードの経路もいっしょに表示させたいのですが、この場合あるノードのleftとright両方が選ばれることになります。これらの情報は２分木を作成したときに、各ノードの情報として、left=0、right=1、both=3などとしてどの枝が選ばれたかを書き込んでおいて、rootから辿るようにしています。
この場合、bothにたどり着いた時点で、leftとrightを順番に再帰的に呼び出すと、後に呼んだ
rightの分岐前までのノードの情報がなくなるので、とりあえず、ベクターにこの情報を入れて
おいて、後から欠落したノードの情報を前の経路のノード情報から埋めて使うようにしているの
ですがかなり大変です。（特に何重にも分岐した場合にも対応しないといけないので。）
とりあえず、作ってみて問題なく表示してくれるようにはなったのですが、このあたり既に
ご経験のある方で、もっと簡単でいい方法があるよという場合はご教示願えたらと思います。

質問者からの補足コメント

• 上の例で言えば、
  0->1->3
  または0
  0->2
  みたいな話です。
  経路が一位ならrootからノードを辿って表示させればいいだけの話ですが、
  経理が複数あった場合、その経路をどうやって表示させるのが一番効率的か？
  という話です。

  No.1の回答に寄せられた補足コメントです。 補足日時：2019/02/20 05:02

• 

  ノードの名前は、root = (i, j) = (0, W) = (0,5)からはじめて、
  i番目の品物からその品物を取らなかったか取ったかで、
  (1, 5)（leftで品物を取らなかった）、(1, 3)（rightで品物を取った）
  というように名前を付けて行っています。
  
  経路探索でとりあえずベクターに
  {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0) (2 2) (3 2) (4 0)}
  を入れておいて、それを
  {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}
  {(2, 2) (3, 2) (4 ,0)}
  の２つに分割して、後の経路に抜けた部分を加えて、
  {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}
  {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}
  みたいな処理をしています。

  No.2の回答に寄せられた補足コメントです。 補足日時：2019/02/20 10:38

• DPで書くと、
  dp[n][j] = 0
  j<w[i] の時、
  dp[i][j] = dp[i+1][j]
  j>=w[i] の時、
  dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])
  （ここで、w[i] 及びv[i]は、i番目の品物の重さと価値）
  のアルゴリズムで２分木の各ノードにvalue（=dpの値）とdirectionの値を
  書き込んでいきます。最終的には、root=(0, 5)のvalueの値がmax valueになります。
  あとは、このrootから書き込まれたdirectionの方向を辿っていくだけです。

  No.3の回答に寄せられた補足コメントです。 補足日時：2019/02/21 16:38

• ちょっと書き方が悪かったかもしれませんが、DPは使っていません。
  DPと同じアルゴリズムを２分木でやっているということです。
  ２分木ノードを末端まで作った後で、上に向かってこのアルゴリズムでvalueとdirection
  を計算していっています。

  No.4の回答に寄せられた補足コメントです。 補足日時：2019/02/22 01:29

• この件は、２番目の補足の説明の中で書いています。
  rootから辿っていって、directionがbothの場合、最初にleftを
  再帰的に呼び出して、続いてrightを呼び出しているだけです。
  この場合、right側の欠落情報は(0,5)(1,3)です。
  最終的に表示してほしい解は、
  {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}
  {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}
  の２つです。

  No.5の回答に寄せられた補足コメントです。 補足日時：2019/02/22 01:54

• ノードの名前の付け方は補足の２に書いた通りです。
  もし単純に、経路が一位に決まるなら、上の場合だと、rootから辿って
  (0, 5) (1, 3) (2, 3) (3, 0) (4, 0)
  を表示して終わりになります。
  でもこの場合は、解は２つ存在してノード(1,3)のdirectionはbothになっています。
  なので、上の経路を辿った後に、再びbothの所に戻ってきて（bothの所では単純に
  leftに再帰的に分岐させた後、rigthに分岐させるように書いているからです。）
  right側の (2, 2) (3, 2) (4, 0)を辿ります。
  なので、ベクターに入る情報は、
  {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0) (2, 2) (3, 2) (4, 0)}
  になります。
  これ以上に簡単にやる方法ってありますか？

  No.6の回答に寄せられた補足コメントです。 補足日時：2019/02/23 03:52

• ベクターの情報が、{ABCB'C'C''}のように分岐した場合、（分岐図を描いてみてください。）
  単純にノードに保存すると、{ABC}、{AB'C'}、{B'C"}になってしまいませんか？
  私のやり方だと、ベクターに分岐の情報さえあれば、それを
  {ABC}
  {B'C'}
  {C"}
  の３つに分割後、
  １番目と２番目のベクター情報から２番目に欠落しているAの情報を２番目に加えて、
  {ABC}
  {AB'C'}
  {C"}
  同様に２番目と３番目のベクター情報から３番目に欠落しているAB'の情報を２番目に加えて、
  {ABC}
  {AB'C'}
  {AB'C"}
  となります。
  この方法だとどんな分岐が起こっても、ベクター情報だけから複数のパスが正しく再現できます。

  No.7の回答に寄せられた補足コメントです。 補足日時：2019/02/25 17:55

• ごめんなさい。
  ２番目の保存内容が、B'ではなくAB'になるのを見落としていました。
  多分どちらの方法でもできると思います。
  私のは先にベクターを作ってから、その後配列に入れています。

  No.8の回答に寄せられた補足コメントです。 補足日時：2019/02/25 20:16

No.7 ベストアンサー 回答者： siffon9 回答日時： 2019/02/23 19:41

こんにちは、No.2です。

（何故"プンプン"？）

ナップサック問題云々はあまり関係なくて、
要は二分木の複数の経路情報をどうやって保持するかって質問ですね。


> なので、ベクターに入る情報は、
> {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0) (2, 2) (3, 2) (4, 0)}
> になります。

No.6さんの仰るとおり、一つの「ベクター」に複数の経路情報を追加していくのが意味不明です。


以下の様にすれば良いのではないでしょうか。

１．「ベクター」は配列にする、配列の一つの要素に一つの経路情報を保持させる。

２．ノードをルートから辿ってbothのノードになったら其処までの経路情報を一時保管する
　　ノードに保管場所を設ける
　　補足での例だと、(1,3)ノードに{(0, 5) (1, 3)｝を一時保存

３．leftノードの経路を最後までたどり、取得した経路情報を配列「ベクター」に要素として追加
　　Vec[0] = {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}

４．ノードを戻りbothノードまで戻ったら、一時保存した経路情報{(0, 5) (1, 3)｝を取り出す

５．４の経路情報にrightノードを最後までたどった経路情報を追記していく
　　{(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}

６、５の経路情報を配列「ベクター」に要素として追加
　　Vec[1] = {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}


これで複数の経路情報が取得できます
　Vec[0] = {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}
　Vec[1] = {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}

No.8 回答者： siffon9 回答日時： 2019/02/25 19:36

> ベクターの情報が、{ABCB'C'C''}のように分岐した場合、（分岐図を描いてみてください。

）
> 単純にノードに保存すると、{ABC}、{AB'C'}、{B'C"}になってしまいませんか？

最初の質問からそうなのですが
質問者様にしか理解できない表現を説明もなしに使用するのは止めて下さい。
さっぱり分かりません。
だいたい「ベクターの情報」が「分岐」ってなんですか？


> 単純にノードに保存すると、{ABC}、{AB'C'}、{B'C"}になってしまいませんか？

無理矢理解釈して、AとB'がbothノードだと仮定すると
１．ノードAで{A}を一時保存
２．ノードB側をたどり、Vec[0] = {A,B,C}となる
３．ノードAに戻る、一時保存した{A}を取り出す
４．ノードB'へ移動、取り出した{A}にB’を追加→{A,B'}
５．ノードB'で{A,B'}を一時保存
６．ノードC'側をたどり、Vec[1] = {A,B',C'}となる
７．ノードB'に戻る、一時保存した{A,B'}を取り出す
８．ノードC''へ移動、取り出した{A,B'}にC''を追加→{A,B',C''}
　　Vec[2] = {A,B',C''}

「ベクター」には、ちゃんと経路が保存されます。
Vec[0] = {A,B,C}
Vec[1] = {A,B',C'}
Vec[2] = {A,B',C''}
　　
念の為に書きますが、No.7で書いた２～６の手順も、ここで書いた１～８の動作も再帰関数内の処理になります。


疲れた。


> この方法だとどんな分岐が起こっても、ベクター情報だけから複数のパスが正しく再現できます。

じゃあ、その方法で良いじゃん。

No.6 回答者： Tacosan 回答日時： 2019/02/23 00:20

う～ん....

「経路探索」で作った「{(0, 5) (1, 3) (2, 3) (3, 0) (4, 0) (2 2) (3 2) (4 0)}」という「ベクター」だけど
・これはどのような意味を持っていて
・どのように作った
のでしょうか?

単純に複数の「経路」を個別に記憶すればいいだけなのに, 「工夫」して上のような「ベクター」を作ったために却って困っているように見えるなぁ.

No.5 回答者： Tacosan 回答日時： 2019/02/22 01:39

どんな 2分木なのかけっきょくよくわからんのだけど, 2分木をたどるだけなら基本的には

再帰
でいいのでは?

もともとの質問文の
「bothにたどり着いた時点で、leftとrightを順番に再帰的に呼び出すと、後に呼んだ
rightの分岐前までのノードの情報がなくなる」
というところで
・どのように「再帰的」に呼び出していて
・「後に呼んだrightの分岐前までのノードの情報がなくなる」がどのような問題なのか (「期待する動作」と「実際の動作」がどのように違うのか)
が具体的に書かれていないのでなんともいいにくいんだけど.

No.4 回答者： Tacosan 回答日時： 2019/02/22 00:17

変に色気を出して

DP で表を作るついでに覚えていこう
とするよりも, あきらめて
DP が終わってから改めてたどっていく
方が簡単だと思うな.

No.3 回答者： Tacosan 回答日時： 2019/02/20 23:54

ちとかくにん.

「2分木うんぬん」はおいておくとして, ナップザック問題そのものはどのように解くつもり?

No.2 回答者： siffon9 回答日時： 2019/02/20 05:22

こんにちは

No.1様への補足をみましたが
No.1様の「その「２分木」ではなにをどのように格納しているの?」の補足になっていませんよね。

それが分からなければ、ご質問の回答はできないと思いますよ。


> とりあえず、作ってみて問題なく表示してくれるようにはなったのですが

とのことですので、長くなければ現在動作しているプログラムをご提示された方が良いかもしれませんね。

No.1 回答者： Tacosan 回答日時： 2019/02/20 00:05

「２分木を使って２分木ノードの経路もいっしょに表示させたい」というのが, なにをしたいのかさっぱりわからない.

「２分木ノードの経路」ってなに? その「２分木」ではなにをどのように格納しているの?