|
|
目標値を越えず、数値の合計値が最大(目標値との差が最小)
となる数値の組み合わせを求める
組み合わせを利用して探索する
N個の中から1個選ぶ組み合わせ
N個の中から2個選ぶ組み合わせ
N個の中から3個選ぶ組み合わせ
:
N個の中からN個選ぶ組み合わせ
総探索数は COMB(N,1)+COMB(N,2)+...+COMB(N,N)=2^N-1
DECLARE EXTERNAL FUNCTION COMB
PUBLIC NUMERIC MAXSIZE,MSIZE,B(20),EPS
PUBLIC STRING T$(20),TT$(20)
DIM A(20),C(20),TI$(20),TEMP(20) !'個数は10～15程度を想定
LET N=1
LET EPS=0
LET SUM=0
DO
INPUT PROMPT "数値(" & STR$(N) & ") ":A(N) !'(ファイルサイズ、演奏時間等)
IF A(N)=0 THEN !' ０で入力終了
LET N=N-1
EXIT DO
END IF
LET SUM=SUM+A(N)
!' INPUT PROMPT "タイトル(" & STR$(N) & ") ":T$(N) !'(ファイル名、曲名等)
LET N=N+1
LOOP
INPUT PROMPT "目標値=":MAXSIZE !'(メディア容量、空き容量等)
IF MAXSIZE >= SUM THEN
CALL DISPLAY(N,A,T$)
STOP
END IF
!' INPUT PROMPT "許容範囲=":EPS !'目標値 - 合計値 <= 許容範囲 となる組み合わせの表示
LET MMIN=MAXSIZE
LET K=0
DO
LET K=K+1
FOR I=1 TO N
IF A(I) >= MAXSIZE/K THEN EXIT DO
NEXT I
LOOP UNTIL K=N
FOR R=K TO N-1
LET MSIZE=MAXSIZE
MAT TEMP=ZER
LET RR=R
CALL COMB(A,N,RR,TEMP,1)
IF MSIZE < MMIN THEN
LET MMIN=MSIZE
MAT C=B
MAT TI$=TT$
END IF
NEXT R
IF MMIN > 0 THEN CALL DISPLAY(N,C,TI$)
END
EXTERNAL SUB COMB(X(),N,R,A(),K)
IF R=0 THEN
LET S=0
FOR I=1 TO N
IF A(I)=1 THEN
LET S=S+X(I)
END IF
IF S > MAXSIZE THEN EXIT SUB
NEXT I
IF MAXSIZE >= S AND MAXSIZE-S <= MSIZE THEN
LET MSIZE=MAXSIZE-S
MAT B=ZER
MAT TT$=NUL$
LET M=0
FOR J=1 TO N
IF A(J)=1 THEN
LET M=M+1
LET B(M)=X(J)
LET TT$(M)=T$(J)
END IF
NEXT J
IF MSIZE <= EPS THEN
CALL DISPLAY(N,B,TT$)
END IF
END IF
ELSE
FOR I=K TO N-R+1
LET A(I)=1
CALL COMB(X,N,R-1,A,I+1)
LET A(I)=0
NEXT I
END IF
END SUB
EXTERNAL SUB DISPLAY(N,A(),K$())
LET S=0
FOR I=1 TO N
IF A(I)<>0 THEN
PRINT "No.";I;":";A(I);" ";K$(I)
LET S=S+A(I)
END IF
NEXT I
PRINT "計";S;"残差";MAXSIZE-S
END SUB
ex.1
目標値と合計値との差が最小となる組み合わせ
37 39 43 69 75 81 88 108 120 122 128
目標値 700
ex.2
必ずしも目標値と合計値は一致しない
20 23 26 44 54 58 75 78 90 95 110 132
目標値 700
|
|