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.08s 30656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 3 15
2 3 14
3 1 10
4 1 13
5 1 16
6 2 15
7 1 15

5 5 68 1011000
5 5 71 1010100
5 5 70 1010001
5 4 55 1010000
5 5 74 1001100
5 5 73 1001001
5 4 58 1001000
5 5 76 1000101
5 4 61 1000100
5 5 75 1000010
5 4 60 1000001
5 3 45 1000000
5 5 65 0111000
5 5 68 0110100
5 5 67 0110001
5 4 52 0110000
5 5 71 0101100
5 5 70 0101001
5 4 55 0101000
5 5 73 0100101
5 4 58 0100100
5 5 72 0100010
5 4 57 0100001
5 3 42 0100000
5 5 69 0011110
5 4 54 0011101
5 3 39 0011100
5 5 68 0011011
5 4 53 0011010
5 3 38 0011001
5 2 23 0011000
5 5 71 0010111
5 4 56 0010110
5 3 41 0010101
5 2 26 0010100
5 4 55 0010011
5 3 40 0010010
5 2 25 0010001
5 1 10 0010000
5 5 74 0001111
5 4 59 0001110
5 3 44 0001101
5 2 29 0001100
5 4 58 0001011
5 3 43 0001010
5 2 28 0001001
5 1 13 0001000
5 4 61 0000111
5 3 46 0000110
5 2 31 0000101
5 1 16 0000100
5 3 45 0000011
5 2 30 0000010
5 1 15 0000001
5 0 0 0000000

5 76 1000101
https://ideone.com/jk514t
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!