SHARE
TWEET

Plecak(Dynamiczne)

Danielos168 Nov 20th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace kolosdynamiczny_przedmiotyc
  8. {
  9.     class Program
  10.     {
  11.  
  12.         static int Plecak(int pojemnosc, int przedmioty, int[] wagi)
  13.         {
  14.             int[,] wyniki = new int[przedmioty + 1, pojemnosc + 1];
  15.             int[,] kroki = new int[przedmioty + 1, pojemnosc + 1];
  16.             for (int i = 1; i < przedmioty + 1; i++)
  17.             {
  18.  
  19.                 for (int j = 1; j < pojemnosc + 1; j++)
  20.                 {
  21.                     if (wyniki[i - 1, j] >= wyniki[i, j - 1])
  22.                     {
  23.                         wyniki[i, j] = wyniki[i - 1, j];
  24.                         kroki[i, j] = 1; // z góry
  25.                     }
  26.                     else
  27.                     {
  28.                         wyniki[i, j] = wyniki[i, j - 1];
  29.                         kroki[i, j] = 2; // z lewej
  30.                     }
  31.                     if (j >= wagi[i - 1])
  32.                     {
  33.                         wyniki[i, j] = wyniki[i - 1, j - wagi[i - 1]] + wagi[i - 1];
  34.                         kroki[i, j] = 3;
  35.                     }
  36.                 }
  37.  
  38.             }
  39.  
  40.  
  41.  
  42.             bool[] Przedmiotywziete = new bool[przedmioty];
  43.             for (int i = 0; i < Przedmiotywziete.Length; i++)
  44.             {
  45.                 Przedmiotywziete[i] = false; // brak przedmiotu
  46.             }
  47.             int row = przedmioty;
  48.             int column = pojemnosc;
  49.  
  50.             while (column > 0 && row > 0)
  51.             {
  52.                 if (kroki[row, column] == 1)
  53.                 {
  54.  
  55.                     row--;
  56.                 }
  57.                 if (kroki[row, column] == 2)
  58.                 {
  59.                     column--;
  60.                 }
  61.                 if (kroki[row, column] == 3)
  62.                 {
  63.                     // dostalem przedmiot
  64.                     Przedmiotywziete[row - 1] = true;
  65.                     column = column - wagi[row - 1];
  66.                     row--;
  67.                 }
  68.             }
  69.  
  70.  
  71.             for (int i = 0; i < Przedmiotywziete.Length; i++)
  72.             {
  73.                 if (Przedmiotywziete[i] == true)
  74.                 {
  75.                     int c = i + 1;
  76.                     Console.WriteLine("Wzieto przedmiot nr " + c + " o wadze " + wagi[i]);
  77.                 }
  78.             }
  79.  
  80.  
  81.             return wyniki[przedmioty, pojemnosc];
  82.         }
  83.  
  84.  
  85.  
  86.         static void Main(string[] args)
  87.         {
  88.  
  89.  
  90.             int pojemnosc = 18;
  91.             int[] wagi = { 1, 4, 5, 1, 3, 8 };
  92.             int przedmioty = wagi.Length;
  93.             Console.WriteLine("suma wag przedmiotow: " + Plecak(pojemnosc, przedmioty, wagi));
  94.             Console.ReadKey();
  95.         }
  96.     }
  97. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top