30 lines
662 B
Python
30 lines
662 B
Python
n, G = 5, 5 # KNAPSACK 0-1 DANILIN
|
|
N = n + 1 # rextester.com/BCKP19591
|
|
a = 2 ** N
|
|
L, C, j, q, s, d, e = [1]*n, [1]*n, [1]*n, [0]*a, [0]*a, [0]*a, [""]*a
|
|
|
|
from random import randint
|
|
for i in range(n):
|
|
L[i] = randint(1, 3)
|
|
C[i] = 10+randint(1, 9)
|
|
print(i+1, L[i], C[i])
|
|
print()
|
|
|
|
for h in range(a-1, (a-1)//2, -1):
|
|
b = str(bin(h))
|
|
e[h] = b[3:len(b)]
|
|
|
|
for k in range(n):
|
|
j[k] = int(e[h][k])
|
|
q[h] = q[h]+L[k]*j[k]*C[k]
|
|
d[h] = d[h]+L[k]*j[k]
|
|
|
|
if d[h] <= G:
|
|
print(e[h], G, d[h], q[h])
|
|
print()
|
|
|
|
max, m = 0, 1
|
|
for i in range(a):
|
|
if d[i] <= G and q[i] > max:
|
|
max, m = q[i], i
|
|
print(d[m], q[m], e[m])
|