# Knapsack 0-1 Python binary & rosettacode & WE

Discussion in 'Python' started by DANILIN, Jun 1, 2022.

Tags:
1. ### DANILINNew Member

Joined:
Oct 24, 2018
Messages:
6
4
Trophy Points:
3
Gender:
Male
Knapsack 0-1 Python binary & rosettacode & WE

Classic Knapsack problem is solved in many ways

Contents: rosettacode.org/wiki/Knapsack_problem

My newest program synthesizes all ciphers from 0 & 1
adding an extra register and 0 remain on left in cipher

Number of comparisons decreases from N! to 2^N
for example N=10 & N!=3628800 >> 2^N=1024

Random values origin are automatically assigned
quantity and quality and integral of value is obtained
and in general: integral of quantity and quality
and it is possible to divide only anyone will not understand

Code:
```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])```
Main thing is very brief and clear to even all

Results is reduced manually:

Code:
```# Mass Cost
1 2 12
2 3 17
3 1 14
4 3 17
5 1 13
Chifer Mass Cost
11000 5 5 75
01001 5 4 64
00111 5 5 78 !!!
00110 5 4 65
00101 5 2 27
Mass MAX Chifer
5 78 00111```

shabbir likes this.