部分和問題

 投稿者：山中和義  投稿日：2012年 3月18日(日)09時58分10秒
  部分和問題
　与えられたn個の整数a1,a2,…,anから部分集合をうまく選んで、
　その集合内の数の和が与えられた数N（0≦N≦Σak）に等しくなるようにできるかどうかを判定する。


組合せと2進法のビットパターンを対応させる場合、O(2^n)となりますが、
1～Nまでの配列が確保できれば、O(n*N)で算出できます。



!部分和問題（Subset Sum Problem）を動的計画法（Dynamic Programming）で解く

LET C=8 !個数
DATA 1,2,3,4,6,8,12,24 !集合　※正の整数

DIM D(C)
MAT READ D


LET S=0 !総和 Σak
FOR i=1 TO C
   LET S=S+D(i)
NEXT i


DIM W(0 TO S) !整数1～Sを部分集合の和で表す
LET W(0)=0
FOR i=1 TO S
   LET W(i)=-1
NEXT i

LET k=1 !集合から１つ要素を取り出す
DO WHILE k<=C
   LET M=D(k)

   FOR i=S TO 0 STEP -1 !最後からみていき、-1以外のインデックスをiとする
      IF W(i)<>-1 THEN
         LET t=i+M
         IF t<=S AND W(t)=-1 THEN LET W(t)=M
      END IF
      IF W(S)<>-1 THEN EXIT DO !部分和が見つかれば、終了する
   NEXT i

   LET k=k+1
LOOP
!!!MAT PRINT W; !debug


FOR i=1 TO S
   IF W(i)<>-1 THEN
      PRINT i;"= {";

      LET T=i !部分和を表示する
      DO WHILE T>0
         PRINT STR$(W(T));
         LET T=T-W(T)
         IF T>0 THEN PRINT ",";
      LOOP
      PRINT "}"
   END IF
NEXT i

END


実行結果

1 = {1}
2 = {2}
3 = {2,1}
4 = {3,1}
5 = {3,2}
6 = {3,2,1}
7 = {4,2,1}
8 = {4,3,1}
9 = {4,3,2}
10 = {4,3,2,1}
11 = {6,3,2}
12 = {6,3,2,1}
13 = {6,4,2,1}
14 = {6,4,3,1}
15 = {6,4,3,2}
16 = {6,4,3,2,1}
17 = {8,4,3,2}
18 = {8,4,3,2,1}
19 = {8,6,3,2}
20 = {8,6,3,2,1}
21 = {8,6,4,2,1}
22 = {8,6,4,3,1}
23 = {8,6,4,3,2}
24 = {8,6,4,3,2,1}
25 = {12,6,4,2,1}
26 = {12,6,4,3,1}
27 = {12,6,4,3,2}
28 = {12,6,4,3,2,1}
29 = {12,8,4,3,2}
30 = {12,8,4,3,2,1}
31 = {12,8,6,3,2}
32 = {12,8,6,3,2,1}
33 = {12,8,6,4,2,1}
34 = {12,8,6,4,3,1}
35 = {12,8,6,4,3,2}
36 = {12,8,6,4,3,2,1}
60 = {24,12,8,6,4,3,2,1}

 		 

部分和問題

 投稿者：永野護  投稿日：2012年 3月21日(水)11時06分0秒
  いつもありがとうございます。参考にさせていただきます。  

パズル　おもりの個数

 投稿者：山中和義  投稿日：2012年 3月22日(木)13時22分58秒
  > No.1819[元記事へ]

> 部分和問題
> 　与えられたn個の整数a1,a2,…,anから部分集合をうまく選んで、
> 　その集合内の数の和が与えられた数N（0≦N≦Σak）に等しくなるようにできるかどうかを判定する。

パズルの解法に用いてみました。


!問題
!今、1gと10gと25gの3種類のおもりがある。
!この3種類のおもりを用いて（何個使ってもよい）、
!指定された重さを、おもりの個数が最少になるように計る。
!そのとき、3種類のおもりのそれぞれの個数を求めよ。

!参考サイト
!　　パズル問題 シリーズ


DATA 3 !種類
DATA 1,10,25 !おもり
LET M=58 !計りたい重さ


READ N !種類

DIM A(N) !おもり
MAT READ A


!それぞれの重さの1,2,2^2,2^3,…個のおもさを考える。
!すなわち、
!　1, 1*2, 1*2^2, 1*2^3,…
!　10, 10*2, 10*2^2, 10*2^3,…
!　25, 25*2, 25*2^2, 25*2^3,…
!を全体集合と考えて、その部分和に帰着させる。

DIM F(0 TO M) !0からMまで
FOR i=1 TO M
   LET F(i)=-1
NEXT i

LET x=0 !おもりを2^xずつ増やしていく
DO
   FOR k=1 TO N
      LET w=A(k)*2^x

      FOR i=M TO 0 STEP -1 !最後からみていく
         IF F(i)<>-1 THEN
            LET t=i+w
            IF t<=M AND F(t)=-1 THEN !最初に見つかったものが、最少個数となる
               LET F(t)=w
               IF t=M THEN EXIT DO !部分和が見つかれば、終了する
            END IF
         END IF
      NEXT i

   NEXT k
   LET x=x+1 !次へ
LOOP
MAT PRINT F; !debug



DIM C(N) !求めるおもりの個数
MAT C=ZER

PRINT M;"= {"; !部分和を表示する
LET T=M
DO WHILE T>0 !リンクを辿っていく
   PRINT STR$(F(T));

   FOR i=N TO 1 STEP -1 !重いおもりから
      IF MOD(F(T),A(i))=0 THEN !そのおもりで計ることができるなら、
         LET C(i)=C(i)+INT(F(T)/A(i)) !これが最少なので、個数を求める
         EXIT FOR
      END IF
   NEXT i

   LET T=T-F(T) !次へ
   IF T>0 THEN PRINT ",";
LOOP
PRINT "}"

MAT PRINT C; !解を表示する


END

 		 

戻る