OPTION BASE 0
LET KS=50
DIM G(7,2)
LET G(1,1)=24
LET G(2,1)=19
LET G(3,1)=13
LET G(4,1)=9
LET G(5,1)=5
LET G(6,1)=4
LET G(7,1)=2
LET G(1,2)=10800
LET G(2,2)=9500
LET G(3,2)=9100
LET G(4,2)=7200
LET G(5,2)=4500
LET G(6,2)=4000
LET G(7,2)=5000
PUBLIC NUMERIC VMAX
LET VMAX=0
CALL try(1,KS,0,7,KS,G)
PRINT "価値=";VMAX
PRINT
END

EXTERNAL SUB try(P,R, V0, N,A,W(,))    !バックトラック法で検索する
FOR i=0 TO MIN(1,INT(R/W(P,1)))        !詰め込む（枝刈り）　※ビットパターン
   LET RR=R-W(P,1)*i                   !残り
   LET VV=V0+W(P,2)*i                  !価値
   IF RR>0 AND P<N THEN                !n種類まで（深さ優先）
      CALL try(P+1,RR, VV, N,A,W)
   ELSE
      IF VV>=VMAX THEN                  !ここまでの結果を得る
         LET VMAX=VV
      END IF
   END IF
NEXT i
END SUB