31 lines
650 B
Python
31 lines
650 B
Python
n=5; N=n+1; G=5; a=2**N # KNAPSACK 0-1 DANILIN
|
|
L=[];C=[];e=[];j=[];q=[];s=[] # rextester.com/BCKP19591
|
|
d=[];L=[1]*n;C=[1]*n;e=[1]*a
|
|
j=[1]*n;q=[0]*a;s=[0]*a;d=[0]*a
|
|
|
|
from random import randint
|
|
for i in range(0,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=0; m=1
|
|
for i in range(a):
|
|
if d[i]<=G and q[i]>max:
|
|
max=q[i]; m=i
|
|
print (d[m], q[m], e[m])
|