Рюкзак Knapsack и МЫ
Задача Рюкзак 0-1 двоичный Knapsack
Требуется интегрально собрать набор из множества предметов,
имеющих ценность и массу, ограничив максимум массы,
с целью получить наибольшую ценность.
Понимая: вещь в наборе либо есть, либо нет, составляются
всевозможные комбинации N элементов в количестве =2^N,
например при N=5 синтезируются шифры от 00000 до 11111
и в результате выясняется наиболее ценный интегральный набор.
Алгоритм Рюкзак 0-1 двоичный Knapsack реализован на многих языках
программирования и проверяется через интернет онлайн компиляторы.
Алгоритмы: Rosetta Code или RosettaCode
Knapsack qb64 old Рюкзак
qb64forum.alephc.xyz/index.php?topic=3091
qb64forum.alephc.xyz/index.php?topic=2550
Knapsack 0-1 Danilin qb64 new Рюкзак
qb64phoenix.com/forum/showthread.php?tid=463
Knapsack 0-1 c# Рюкзак
csharpforums.net/threads/knapsack-0-1-c-binary-rosettacode-we.8108
bytes.com/topic/c-sharp/insights/977375-knapsack-0-1-c-binary-rosettacode-we
bytes.com/topic/python/insights/978063-knapsack-0-1-python-binary-rosettacode-we
bytes.com/topic/c/insights/978293-knapsack-0-1-c-binary-we
bytes.com/topic/javascript/insights/978412-knapsack-0-1-javascript-binary-rosettacode-we
33 кБ Word
kenokeno.ucoz.ru/doc/rjukzak_01_knapsack.docx
kenokeno.ucoz.ru/doc/KNAPSACK.pdf
kenokeno.ucoz.ru/doc/KNAPSACK.docx
500 кБ Excel
kenokeno.ucoz.ru/doc/rjukzak_01_knapsack.xlsx
Knapsack 0-1 Python Рюкзак
python-forum.io/thread-37333.html
trinket.io/embed/python/dc6398732d
<iframe src="https://trinket.io/embed/python/dc6398732d" width="100%" height="356" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>
Knapsack Python & qb64
rextester.com/KMDD4803
Knapsack Basic Рюкзак
jdoodle.com/iembed/v0/suj
Knapsack C++ Рюкзак
rextester.com/VCBSQ91995
Рюкзак 0-1 & rosettacode & qbasic qb64 и МЫ
Классическая задача про рюкзак решается многими способами
оглавление: rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1
Темы и программы: Knapsack
qb64phoenix.com/forum/showthread.php?tid=463
qb64forum.alephc.xyz/index.php?topic=3091
Новейшая моя программа синтезирует все шифры 0 и 1
добавляя лишний регистр и 0 остаются слева в шифре
Количество сравнений уменьшается с N! до 2^N
например N=5 N!=120 >> 2^N=32
Автоматически присваиваются случайные значения
количества и качества и получается интеграл стоимости
причём возможно и делить только любой человек не поймёт
Программа пишет в каталог qb64
Open "knapsack.txt" For Output As #1 'knapsack.bas DANILIN
N=7: L=5: a = 2^(N+1): Randomize Timer ' qb64 qbasic
Dim L(N), C(N), j(N), q(a), q$(a), d(a)
For m=a-1 To (a-1)/2 Step -1: g=m: Do ' sintez cipher
q$(m)=LTrim$(Str$(g Mod 2))+q$(m)
g=g\2: Loop Until g=0
q$(m)=Mid$(q$(m), 2, Len(q$(m)))
Next
For i=1 To N: L(i)=Int(Rnd*3+1) ' lenght & cost
C(i)=10+Int(Rnd*9): Print #1, i, L(i), C(i): Next ' origin
For h=a-1 To (a-1)/2 Step -1
For k=1 To N: j(k)=Val(Mid$(q$(h), k, 1)) ' from cipher
q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
d(h)=d(h)+L(k)*j(k)
Next
If d(h) <= L Then Print #1, d(h), q(h), q$(h)
Next
max=0: m=1
For i=1 To a: If d(i)<=L Then If q(i) > max Then max=q(i): m=i
Next
Print #1,: Print #1, d(m), q(m), q$(m): End
Knapsack 0-1 & rosettacode & qbasic qb64 & WE
Classic Knapsack problem is solved in many ways
Contents: rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1
Topics & long programs: Knapsack
qb64phoenix.com/forum/showthread.php?tid=463
qb64forum.alephc.xyz/index.php?topic=3091
Combinations Generator
qb64forum.alephc.xyz/index.php?topic=2999
bytes.com/topic/c-sharp/insights/977375-knapsack-0-1-c-binary-rosettacode-we
bytes.com/topic/python/insights/978063-knapsack-0-1-python-binary-rosettacode-we
bytes.com/topic/c/insights/978293-knapsack-0-1-c-binary-we
bytes.com/topic/javascript/insights/978412-knapsack-0-1-javascript-binary-rosettacode-we
My newest program synthesizes all ciphers from 0 & 1
adding an extra register & 0 remain on left in cipher
Number of comparisons decreases from N! to 2^N
for example N=5 N!=120 >> 2^N=32
Random values origin are automatically assigned
quantity & quality & integral of value is obtained
& it is possible to divide only anyone will not understand
Program write results to qb64 directory
Main thing is very brief & clear to even all
Results is reduced manually:
1 2 17
2 2 14
3 2 17
4 1 11
5 2 18
6 3 14
7 3 10
5 73 1101000
4 62 1100000
5 79 1011000
4 68 1010000
2 28 0100000
5 81 0011100 !!!
3 45 0011000
4 70 0010100
5 76 0010010
2 36 0000100
5 81 0011100
Результат сокращён вручную
Главное очень кратко и понятно даже школьникам
Рюкзак 0-1 Питон Python KNAPSACK 0-1 DANILIN
n=5; N=n+1; G=5; a=2**N # N=7: L=5: a = 2^(N+1): 'knapsack.bas DANILIN
L=[];C=[];e=[];j=[];q=[];s=[] # Dim L(N), C(N), j(N), q(a), q$(a), d(a)
d=[];L=[1]*n;C=[1]*n;e=[1]*a # KNAPSACK 0-1 DANILIN
j=[1]*n;q=[0]*a;s=[0]*a;d=[0]*a
from random import randint # Randomize Timer
for i in range(0,n): # For i=1 To N
L[i]=randint(1,3) # L(i)=Int(Rnd*3+1)
C[i]=10+randint(1,9) # C(i)=10+Int(Rnd*9)
print(i+1,L[i],C[i]) # Print i, L(i), C(i): Next
print()
for h in range(a-1,(a-1)//2,-1):# For m=a-1 To (a-1)/2 Step -1: g=m: Do
b=str(bin(h)) # q$(m)=LTrim$(Str$(g Mod 2))+q$(m): g=g\2: Loop Until g=0
e[h]=b[3:len(b)] # q$(m)=Mid$(q$(m), 2, Len(q$(m))): Next
for k in range (n): # For k=1 To N:
j[k]=int(e[h][k]) # j(k)=Val(Mid$(q$(h), k, 1)) ' from cipher
q[h]=q[h]+L[k]*j[k]*C[k] # q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
d[h]=d[h]+L[k]*j[k] # d(h)=d(h)+L(k)*j(k): Next
if d[h]<= G: # If d(h) <= L Then
print(e[h], G, d[h],q[h])# Print #1, d(h), q(h), q$(h): Next
print()
max=0; m=1 # max=0: m=1:
for i in range(a): # For i=1 To a
if d[i]<=G and q[i]>max: # If d(i)<=L Then If q(i) > max
max=q[i]; m=i # Then max=q(i): m=i: Next
print (d[m], q[m], e[m]) # Print #1,: Print #1, d(m), q(m), q$(m): End
KNAPSACK JavaScript JS
<!DOCTYPE html>
<title>KNAPSACK JavaScript</title> </head> <body> <noscript>Vkluch JS</noscript>
jdoodle.com/h/2Uc
rextester.com/BQYV50962
<script>
var n=12; G=2; a = Math.pow(2,n+1); // KNAPSACKj.js
var dec, i, h, k, max, m, s;
var L=[n], C=[n], j=[n], q=[a], d=[a]; e=[a];
document.write("<br><br># Kol Cena<br>")
document.write("# Amo Price<br><br>")
for (i=0; i<n; i++)
{ L[i]=1+Math.floor(Math.random()*3)
C[i]=10+Math.floor(Math.random()*9); j[i]=0;
document.write( (i+1) +" "+ L[i] +" "+ C[i] +"<br>")
}
for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
document.write("<br>")
document.write("Mx Kol St-st Schifr<br>")
document.write("Mx Amo Price Cipher<br>")
for (h = a-1; h>(a-1)/2; h--)
{ dec=h; e[h]=""
while (dec > 0)
{ s = Math.floor(dec % 2);
e[h] = s + e[h]; dec = Math.floor(dec/2);
}
if (e[h] == "") {e[h] = "0";}
e[h]= e[h].substr(1, e[h].length-1);
for (k=0; k<n; k++)
{ j[k] = Number(e[h].substr(k,1));
q[h]=q[h]+L[k]*j[k]*C[k];
d[h]=d[h]+L[k]*j[k];
}
if (d[h] <= G)
document.write("<br>"+ G +" "+ d[h] +" "+ q[h] +" "+ e[h])
} document.write("<br>")
max=0; m=1;
for (i=0; i<a; i++)
{ if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
}
document.write("<br>"+ d[m] +" "+ q[m] +" "+ e[m] +"<br><br>")
document.write("Mx St-st Schifr<br>")
document.write("Mx Price Cipher<br><br>")
</script>
</body> </html>
C# KNAPSACK 0-1 DANILIN
rextester.com/ZUDP19364
using System;using System.Text; // KNAPSACK 0-1 DANILIN
namespace Knapsack { class Program { static void Main()
{ int n=5; int G=5; int u=n+1; int a=Convert.ToInt32(Math.Pow(2,u));
int[] L = new int[n]; int[] C = new int[n]; int[] j = new int[n];
int[] q = new int[a]; int[] S = new int[a]; int[] d = new int[a];
int dec; int i; string[] e = new string[a];
int h; int k; int max; int m; Random rand = new Random();
for (i=0; i<n; i++) // rextester.com/ZUDP19364
{L[i]=1+rand.Next(3); C[i]=10+rand.Next(9);
Console.WriteLine((i+1) +" "+ L[i] +" " + C[i]);
} Console.WriteLine();
for (h = a-1; h>(a-1)/2; h--)
{ dec=h; while (dec > 0)
{ e[h] = dec % 2 + e[h]; dec/=2; }
if (e[h] == "") e[h]="0";
e[h]=e[h].Substring(1,e[h].Length-1);
for (k=0; k<n; k++)
{ j[k]=Convert.ToInt32(e[h].Substring(k,1));
q[h]=q[h]+L[k]*j[k]*C[k];
d[h]=d[h]+L[k]*j[k];
}
if (d[h]<= G)
{ Console.WriteLine(G +" "+ d[h] +" "+ q[h] +" "+ e[h]);
}
}
max=0; m=1;
for (i=0; i<a; i++)
{ if (d[i]<=G && q[i]>max) { max=q[i]; m=i;}
}
Console.Write("\n"+ d[m] +" "+ q[m] +" "+ e[m]);
}}}
C++ Knapsack Рюкзак 0-1 DANILIN
#include <iostream> // KNAPSACK 0-1 DANILIN
using namespace std; int main()
{ setlocale (LC_ALL, "RUS");
srand(time(NULL)); // rextester.com/VCBSQ91995
{ int n=7; int G=5; int a=2;
int dec, i, h, k, max, m;
for (i=0; i<n; i++) a=2*a; string e[a]; // 2^n
int L[n], C[n], j[n], q[a], d[a];
cout << "# Кол Цена" << endl;
cout << "# Amo Price" << endl << endl;
for (i=0; i<n; i++)
{ L[i]=1+(rand() % 3); C[i]=10+(rand() % 9); j[i]=0;
cout << i+1 << " " << L[i] << " " << C[i] << endl;
}
for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
cout << endl;
cout << "Мх Кол Ст-ть Шифр" << endl;
cout << "Mx Amo Price Cipher" << endl << endl;
for (h = a-1; h>(a-1)/2; h--)
{ dec=h; while (dec > 0)
{ string s(""); s += '0'+dec%2;
e[h] = s + e[h]; dec/=2;
}
if (e[h] == "") {e[h] = "0";}
e[h]= e[h].substr(1, e[h].size()-1);
for (k=0; k<n; k++)
{ j[k] = atoi((char*)(e[h].substr(k,1)).c_str());
q[h]=q[h]+L[k]*j[k]*C[k];
d[h]=d[h]+L[k]*j[k];
}
if (d[h] <= G)
cout << G << " " << d[h] << " " << q[h] << " " << e[h] << endl;
} cout << endl;
max=0; m=1;
for (i=0; i<a; i++)
{ if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
}
cout << "Мх Ст-ть Шифр" << endl;
cout << "Mx Price Cipher" << endl << endl;
cout << d[m] << " " << q[m] << " " << e[m] << endl << endl;}
system("pause");
}
Python online Knapsack 0-1
C# KNAPSACK 0-1 DANILIN
using System; // Knapsack C# binary DANILIN
using System.Text; // rextester.com/YRFA61366
namespace Knapsack
{
class Knapsack
{
static void Main()
{
int n = 7;
int Inside = 5;
int all=Convert.ToInt32(Math.Pow(2,(n+1)));
int[] mass = new int[n];
int[] cost = new int[n];
int[] jack = new int[n];
int[] quality = new int[all];
int[] amount = new int[all];
int i; // circle
int k; // circle
int dec;
string[] bin = new string[all];
int list;
int max;
int max_num;
Random rand = new Random();
for (i=0; i<n; i++)
{
mass[i]=1+rand.Next(3);
cost[i]=10+rand.Next(9);
Console.WriteLine("{0} {1} {2}", i+1, mass[i], cost[i]);
}
Console.WriteLine();
for (list = all-1; list>(all-1)/2; list--)
{
dec=list;
while (dec > 0)
{
bin[list] = dec % 2 + bin[list]; // from 10 to 2
dec/=2;
}
if (bin[list] == "")
{
bin[list] = "0";
}
bin[list]=bin[list].Substring(1,bin[list].Length-1);
for (k=0; k<n; k++) // inside 01
{
jack[k]=Convert.ToInt32(bin[list].Substring(k,1));
quality[list]=quality[list]+mass[k]*jack[k]*cost[k]; // integral of costs
amount[list]=amount[list]+mass[k]*jack[k]; // integral of mass
}
if (amount[list]<= Inside) // current mass < Knapsack
{
Console.WriteLine("{0} {1} {2} {3}", Inside, amount[list], quality[list], bin[list]);
}
}
Console.WriteLine();
max=0;
max_num=1;
for (i=0; i < all; i++)
{
if (amount[i]<=Inside && quality[i]>max)
{
max = quality[i]; max_num =i ;
}
}
Console.WriteLine("{0} {1} {2}",amount[max_num],quality[max_num],bin[max_num]);
}
}
}
Knapsack RosettaCode JavaScript
https://rosettacode.org/wiki/Knapsack_problem/0-1#JavaScript_2
<!DOCTYPE html>
<title>KNAPSACK 22 JavaScript</title> </head> <body> <noscript>Vkluch JS</noscript>
https://jdoodle.com/h/2Ut
<script>
var n=22; G=400; a = Math.pow(2,n+1); // KNAPSACKj.js
var dec, i, h, k, max, m, s;
var L=[n], C=[n], j=[n], q=[a], d=[a]; e=[a];
document.write("<br><br># Kol Cena<br>")
document.write("# Amo Price<br><br>")
L=[ 9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30 ]
C=[ 150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10 ]
for (i=0; i<n; i++)
{ // L[i]=1+Math.floor(Math.random()*3)
// C[i]=10+Math.floor(Math.random()*9);
j[i]=0;
document.write( (i+1) +" "+ L[i] +" "+ C[i] +"<br>")
}
for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
document.write("<br>")
document.write("Mx Kol St-st Schifr<br>")
document.write("Mx Amo Price Cipher<br>")
for (h = a-1; h>(a-1)/2; h--)
{ dec=h; e[h]=""
while (dec > 0)
{ s = Math.floor(dec % 2);
e[h] = s + e[h]; dec = Math.floor(dec/2);
}
if (e[h] == "") {e[h] = "0";}
e[h]= e[h].substr(1, e[h].length-1);
for (k=0; k<n; k++)
{ j[k] = Number(e[h].substr(k,1));
q[h]=q[h]+j[k]*C[k];
d[h]=d[h]+L[k]*j[k];
}
// if (d[h] <= G)
// document.write("<br>"+ G +" "+ d[h] +" "+ q[h] +" "+ e[h])
} document.write("<br>")
max=0; m=1;
for (i=0; i<a; i++)
{ if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
}
document.write("<br>"+ d[m] +" "+ q[m] +" "+ e[m] +"<br><br>")
document.write("Mx St-st Schifr<br>")
document.write("Mx Price Cipher<br><br>")
</script>
</body> </html>
| 
