Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace kolosdynamiczny_przedmiotyc
- {
- class Program
- {
- static int Plecak(int pojemnosc, int przedmioty, int[] wagi)
- {
- int[,] wyniki = new int[przedmioty + 1, pojemnosc + 1];
- int[,] kroki = new int[przedmioty + 1, pojemnosc + 1];
- for (int i = 1; i < przedmioty + 1; i++)
- {
- for (int j = 1; j < pojemnosc + 1; j++)
- {
- if (wyniki[i - 1, j] >= wyniki[i, j - 1])
- {
- wyniki[i, j] = wyniki[i - 1, j];
- kroki[i, j] = 1; // z góry
- }
- else
- {
- wyniki[i, j] = wyniki[i, j - 1];
- kroki[i, j] = 2; // z lewej
- }
- if (j >= wagi[i - 1])
- {
- wyniki[i, j] = wyniki[i - 1, j - wagi[i - 1]] + wagi[i - 1];
- kroki[i, j] = 3;
- }
- }
- }
- bool[] Przedmiotywziete = new bool[przedmioty];
- for (int i = 0; i < Przedmiotywziete.Length; i++)
- {
- Przedmiotywziete[i] = false; // brak przedmiotu
- }
- int row = przedmioty;
- int column = pojemnosc;
- while (column > 0 && row > 0)
- {
- if (kroki[row, column] == 1)
- {
- row--;
- }
- if (kroki[row, column] == 2)
- {
- column--;
- }
- if (kroki[row, column] == 3)
- {
- // dostalem przedmiot
- Przedmiotywziete[row - 1] = true;
- column = column - wagi[row - 1];
- row--;
- }
- }
- for (int i = 0; i < Przedmiotywziete.Length; i++)
- {
- if (Przedmiotywziete[i] == true)
- {
- int c = i + 1;
- Console.WriteLine("Wzieto przedmiot nr " + c + " o wadze " + wagi[i]);
- }
- }
- return wyniki[przedmioty, pojemnosc];
- }
- static void Main(string[] args)
- {
- int pojemnosc = 18;
- int[] wagi = { 1, 4, 5, 1, 3, 8 };
- int przedmioty = wagi.Length;
- Console.WriteLine("suma wag przedmiotow: " + Plecak(pojemnosc, przedmioty, wagi));
- Console.ReadKey();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement