473,372 Members | 953 Online

# Knapsack 0-1 C++ binary & WE

24 16bit
Knapsack 0-1 C++ binary & WE

Classic Knapsack problem is solved in many ways

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

Feature of algorithm:
converts whole into a string
and converts string into a whole
what will help in other programs

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

Expand|Select|Wrap|Line Numbers
1. #include <iostream> // KNAPSACK 0-1 DANILIN
2. using namespace std; int main()
3. { setlocale (LC_ALL, "RUS");
4.   srand(time(NULL)); // rextester.com/VCBSQ91995
5.
6. { int n=7; int G=5; int a=2;
7.   int dec, i, h, k, max, m;
8.   for (i=0; i<n; i++) a=2*a; string e[a]; // 2^n
9.   int L[n], C[n], j[n], q[a], d[a];
10.
11. cout << "#  Amo Price" << endl << endl;
12. for (i=0; i<n; i++)
13. { L[i]=1+(rand() % 3); C[i]=10+(rand() % 9); j[i]=0;
14.   cout << i+1 << "   " << L[i] << "   " << C[i] << endl;
15. for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
16. cout << endl;
17.
18. cout << "Mx Amo Price Chifer" << endl << endl;
19. for (h = a-1; h>(a-1)/2; h--)
20.   { dec=h; while (dec > 0)
21.       { string s(""); s += '0'+dec%2;
22.         e[h] = s + e[h]; dec/=2;
23.       }
24. if (e[h] == "") {e[h] = "0";}
25. e[h]= e[h].substr(1, e[h].size()-1);
26.
27. for (k=0; k<n; k++)
28. { j[k] = atoi((char*)(e[h].substr(k,1)).c_str());
29.   q[h]=q[h]+L[k]*j[k]*C[k];
30.   d[h]=d[h]+L[k]*j[k];
31. }
32.
33. if (d[h] <= G)
34. cout << G << "  " << d[h] << "  " << q[h] << "  " << e[h] << endl;
35. } cout << endl;
36.
37. max=0; m=1;
38. for (i=0; i<a; i++)
39. { if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
40. }
41. cout << "Mx Price Cipher" << endl << endl;
42. cout << d[m] << "  " << q[m] << "  " << e[m] << endl << endl;}
43. system("pause");
44. }
Feb 6 '23 #1
0 371