fork download
copy 
  1. using System;		// Knapsack C# binary DANILIN
  2. using System.Text;	// 
  3. namespace Knapsack 
  4. { class Knapsack  
  5.     { static void Main()
  6.         {   int n = 7; 
  7.             int Inside = 5; 
  8.             int all=Convert.ToInt32(Math.Pow(2,(n+1))); 
  9.             int[] mass = new int[n]; 
  10.             int[] cost = new int[n]; 
  11.             int[] jack = new int[n]; 
  12.             int[] quality = new int[all]; 
  13.             int[] amount = new int[all];   
  14.             int i; 			// circle
  15.             int k; 			// circle
  16.             int dec;  
  17.             string[] bin = new string[all]; 
  18.             int list; 
  19.             int max;
  20.             int max_num;
  21.             Random rand = new Random();
  22.  
  23.             for (i=0; i<n; i++)
  24.             {   mass[i]=1+rand.Next(3);
  25.                 cost[i]=10+rand.Next(9);
  26.                 Console.WriteLine("{0} {1} {2}", i+1, mass[i], cost[i]); 
  27.             } 
  28.             Console.WriteLine();
  29.  
  30.  
  31.             for (list = all-1; list>(all-1)/2; list--) 
  32.             {   dec=list; 
  33.                 while (dec > 0)
  34.                 { bin[list] = dec % 2 + bin[list]; // from 10 to 2 
  35.                     dec/=2; 
  36.                 }
  37.                 if (bin[list] == "")  bin[list] = "0";
  38.  
  39.                 bin[list]=bin[list].Substring(1,bin[list].Length-1); 
  40.                 for (k=0; k<n; k++) // inside 01
  41.                 {   jack[k]=Convert.ToInt32(bin[list].Substring(k,1));
  42.                     quality[list]=quality[list]+mass[k]*jack[k]*cost[k]; 	// integral of costs
  43.                     amount[list]=amount[list]+mass[k]*jack[k]; 	// integral of mass
  44.                 }        
  45.                 if (amount[list]<= Inside)		// current mass < Knapsack
  46.                 { Console.WriteLine("{0} {1} {2} {3}", Inside, amount[list], quality[list], bin[list]); 
  47.                 } 
  48.             } 
  49.             Console.WriteLine();
  50.  
  51.             max=0; 
  52.             max_num=1;
  53.             for (i=0; i < all; i++)
  54.             {  if (amount[i]<=Inside && quality[i]>max)
  55.                 {  max = quality[i]; max_num =i ;
  56.                 }
  57.             }
  58. Console.WriteLine("{0} {1} {2}",amount[max_num],quality[max_num],bin[max_num]);
  59. }}}
  60.  
Success #stdin #stdout 0.06s 30528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 3 12
2 3 15
3 2 14
4 1 17
5 2 14
6 1 15
7 1 13

5 5 64 1010000
5 5 68 1001010
5 5 66 1001001
5 4 53 1001000
5 5 64 1000100
5 5 64 1000011
5 4 51 1000010
5 4 49 1000001
5 3 36 1000000
5 5 73 0110000
5 5 77 0101010
5 5 75 0101001
5 4 62 0101000
5 5 73 0100100
5 5 73 0100011
5 4 60 0100010
5 4 58 0100001
5 3 45 0100000
5 5 73 0011100
5 5 73 0011011
5 4 60 0011010
5 4 58 0011001
5 3 45 0011000
5 5 71 0010110
5 5 69 0010101
5 4 56 0010100
5 4 56 0010011
5 3 43 0010010
5 3 41 0010001
5 2 28 0010000
5 5 73 0001111
5 4 60 0001110
5 4 58 0001101
5 3 45 0001100
5 3 45 0001011
5 2 32 0001010
5 2 30 0001001
5 1 17 0001000
5 4 56 0000111
5 3 43 0000110
5 3 41 0000101
5 2 28 0000100
5 2 28 0000011
5 1 15 0000010
5 1 13 0000001
5 0 0 0000000

5 77 0101010
https://ideone.com/pUTTfb
Knapsack
language:
C# (NET 6.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!