プログラムの依頼その２

 投稿者：GAI  投稿日：2015年 7月25日(土)08時04分1秒
  何度もすみません。
A={1,2,3,4,6,8,12,16,24,32}
の集合に対し
異なるAの要素の和で32を構成するものが何通りあるか知りたいとする。
やり方が分からなかったので、Aの部分集合の全てを作り、それぞれの和を計算させ、
合計のデータ頻度を集計し（これらをやってくれるコマンドは揃っていて割と容易く作業は進められる。）11通りあることが分かった。
1+2+3+6+8+12
2+4+6+8+12
1+2+3+4+6+16
1+3+4+8+16
2+6+8+16
1+3+12+16
4+12+16
1+3+4+24
2+6+24
8+24
32

しかしAの要素の数が多くなると部分集合全てを作る手段をとっているとメモリーが足らなくなるし、なんか非能率的のような気がする。
そこで一般にAの要素を与え（50個くらいは可能な様にしたい。）
このAの異なる要素の和で指定するNの値にできるものが何通りあるか（具体的なAの要素はわからなくてもよい。全部で何通り可能かの数だけを知りたい。）
これを可能とするプログラムを作って欲しいのですが・・・
 		 

Re: プログラムの依頼その２

 投稿者：山中和義  投稿日：2015年 7月25日(土)09時40分8秒
  > No.3784[元記事へ]

GAIさんへのお返事です。

> そこで一般にAの要素を与え（50個くらいは可能な様にしたい。）
> このAの異なる要素の和で指定するNの値にできるものが何通りあるか（具体的なAの要素はわからなくてもよい。全部で何通り可能かの数だけを知りたい。）


これも上限はあります。nの値までの配列がとれれば可能です。

参照　#3621　動的計画法


DATA 32 !値
DATA 10 !データの個数m
DATA 1,2,3,4,6,8,12,16,24,32 !データ

READ X
DIM A(X) !1からxまでの数
MAT A=ZER

READ M

LET S=0
FOR i=1 TO M !ひとつずつ取り出す
   READ D
   FOR P=MIN(S,X-D) TO 1 STEP -1 !部分和を求める
      IF A(P)>0 THEN
         LET T=P+D
         LET A(T)=A(T)+A(P)
      END IF
   NEXT P
   IF D<=X THEN LET A(D)=A(D)+1
   LET S=S+D
NEXT i

PRINT A(X);"通り" !答え（場合の数）

END


 		 

戻る