|
|
問題
商品券が10枚ある。
1000円の商品を買いたい。ただし、おつりは出ない。
ぴったりの組合せはあるか。
答え
その１ 2^10通り
DATA 50,80,130,190,230,250,280,310,390,440
DIM B(0 TO 2^10-1) !添え字がビットパターンとなる
LET B(0)=0
FOR K=0 TO 10-1 !ひとつずつ取り出す
READ D
LET Y=2^(K+1)-1 !部分和を求める
FOR X=2^K-1 TO 0 STEP -1
LET B(Y)=B(X)+D
LET B(Y-1)=B(X)
LET Y=Y-2
NEXT X
!!!MAT PRINT B; !debug
NEXT K
FOR i=0 TO 2^10-1 !答え（すべて）
IF B(i)=1000 THEN PRINT RIGHT$("000000000"&BSTR$(i,2),10)
NEXT i
END
実行結果
0000010101 ← 50,80,130,190,230,250,280,310,390,440
0010110010
0100011010
0100110001
0110110100
1000010110
1000101001
1001111000
1010101100
1100110010
その２ 動的計画法（Dynamic Programming）による
DATA 50,80,130,190,230,250,280,310,390,440
DIM A(1000)
MAT A=ZER
LET S=0
FOR i=1 TO 10 !ひとつずつ取り出す
READ D
FOR P=MIN(S,1000) TO 1 STEP -1 !部分和を求める
IF A(P)>0 THEN
LET T=P+D
IF T<=1000 THEN LET A(T)=A(T)+A(P)
END IF
NEXT P
LET A(D)=A(D)+1
LET S=S+D
NEXT i
PRINT A(1000);"通り" !答え（場合の数）
END
実行結果
10 通り
その３ 動的計画法（Dynamic Programming）による
DATA 50,80,130,190,230,250,280,310,390,440
DIM A(1000)
MAT A=ZER
LET S=0
FOR i=1 TO 10 !ひとつずつ取り出す
READ D
FOR P=MIN(S,1000) TO 1 STEP -1 !部分和を求める
IF A(P)>0 THEN !リンクを形成する（上書きされる）
LET T=P+D
IF T<=1000 THEN LET A(T)=D
END IF
NEXT P
LET A(D)=D
LET S=S+D
NEXT i
LET T=1000 !答え（解の1つ）
DO WHILE T>0
PRINT A(T);
LET T=T-A(T) !リンクをたどる
LOOP
PRINT
END
実行結果
440 310 250
|
|