Knapsack problem/0-1: Difference between revisions

=={{header|BASIC}}==

==={{header|QBasic}}===

{{works with|QBasic|1.1}}

{{works with|QuickBasic|4.5}}

{{trans|QB64}}

<lang qbasic>N = 7: G = 5: a = 2 ^ (N + 1)

RANDOMIZE TIMER

DIM L(N), C(N), j(N), q(a), d(a), q$(a)

FOR i = a - 1 TO (a - 1) \ 2 STEP -1

k = i

DO ' cipher 0-1

q$(i) = LTRIM$(STR$(k MOD 2)) + q$(i)

k = INT(k / 2)

LOOP UNTIL k = 0

q$(i) = MID$(q$(i), 2, LEN(q$(i)))

NEXT i

PRINT " # Mass Cost"

FOR i = 1 TO N

L(i) = INT(RND * 3 + 1)' mass & cost

C(i) = 10 + INT(RND * 9)

PRINT i, L(i), C(i)

NEXT i ' origin

PRINT CHR$(10) + "Mass Cost Chifer"

FOR h = a - 1 TO (a - 1) / 2 STEP -1

FOR k = 1 TO N

j(k) = VAL(MID$(q$(h), k, 1)) ' j() = cipher

q(h) = q(h) + L(k) * j(k) * C(k) ' 0 or 1

d(h) = d(h) + L(k) * j(k)

NEXT k

IF d(h) <= G THEN PRINT d(h), q(h), q$(h)

NEXT h

PRINT CHR$(10) + "Mass MAX Chifer"

max = 0: h = 1

FOR i = 1 TO a

IF d(i) <= G AND q(i) > max THEN max = q(i): h = i

NEXT i

PRINT d(h), q(h), q$(h)</lang>

{{out}}

<pre>Same as QB64 entry.</pre>

==={{header|Yabasic}}===

{{trans|QB64}}

<lang freebasic>N = 7 : G = 5 : a = 2^(N+1)

dim L(N), C(N), j(N), q(a), d(a), q$(a)

for i = a-1 to int((a-1)/2) step -1

k = i

repeat // cipher 0-1

q$(i) = ltrim$(str$(mod(k, 2))) + q$(i)

k = int(k / 2)

until k = 0

q$(i) = mid$(q$(i), 2, len(q$(i)))

next i

print " # Mass Cost"

for i = 1 to N

L(i) = int(ran(3)) + 1 // mass & cost

C(i) = 10 + int(ran(9))

print i, chr$(9), L(i), chr$(9), C(i)

next i // origin

print chr$(10) + "Mass Cost Chifer"

for h = a-1 to (a-1)/2 step -1

for k = 1 to N

j(k) = val(mid$(q$(h), k, 1)) // j() = cipher

q(h) = q(h) + L(k) * j(k) * C(k) // 0 or 1

d(h) = d(h) + L(k) * j(k)

next k

if d(h) <= G print d(h), chr$(9), q(h), chr$(9), q$(h)

next h

print chr$(10) + "Mass MAX Chifer"

maxx = 0 : h = 1

for i = 1 to a

if d(i) <= G and q(i) > maxx maxx = q(i) : h = i

next i

print d(h), chr$(9), q(h), chr$(9), q$(h)

end</lang>

{{out}}

<pre>Same as QB64 entry.</pre>