Statek wycieczkowy zabiera na pokład co najwyżej m pasażerów. Na przystań
przyszło n rodzin liczących odpowiednio k1, ..., kn, członków. Poszczególne rodziny
chcą wejść w całości (wchodzi cała rodzina albo nikt). Skonstruuj rozwiązanie
zachłanne pomagające kapitanowi zabrać na pokład jak najwięcej osób. Oceń
złożoność i zilustruj działanie algorytmu dla samodzielnie wybranych danych.
Jakieś pomysły?
To jest uproszczony problem plecakowy
coś takiego się udało napisać:
static void Knapsack(int c, int[] weight)
{
int w, k;
int l = weight.Length;
int[,] tab = new int[l + 1, c + 1];
for (w = 0; w <= l; w++)
{
for (k = 0; k <= c; k++)
{
if (w == 0 || k == 0)
tab[w, k] = 0;
else if (weight[w - 1] <= k)
tab[w, k] = Math.Max(weight[w - 1] + tab[w - 1, k - weight[w - 1]], tab[w - 1, k]);
else
tab[w, k] = tab[w - 1, k];
}
}
int wynik = tab[l, c];
Console.WriteLine(wynik);
int j = c;
for (int i = l; i > 0; i--)
{
if (wynik == tab[i - 1, j]) continue;
else
{
Console.WriteLine(weight[i - 1] + " ");
wynik -= weight[i - 1];
j -= weight[i - 1];
}
}
}
może da się jakoś uprościć?
Fajne zadanie, wczoraj wieczor mi zniszczylo ;)
Na razie robie to tak ze upycham na statek rodziny dopóki starcza miejsca dla calej, potem szukam algorytmu ktory w skrocie zobaczy ile jeszcze jest miejsc wolnych i posprawdza czy mozna popodmieniac rodziny.
np. zostalo 1 miejsce, wiec wypatruje z zapakowanych rodzine np.5osobowa i szukam czy w tych pozostawionych jest jakas 6osobowa ewentualnie czy są wsrod pozostawionych jakies rodziny ktorych suma daje 6osob. jezeli tak podmieniam
i ten algorytm mnie juz wczoraj wieczorem wymeczyl ;) moze ktos cos podpowie jak to zrobic na petlach - tak slowami. /ten swoj algorytm podmieniajacy wycialem, tu go nie ma - dla lepszej czytelnosci/
Do tej pory mam to:
Kod okna:
public partial class Form1 : Form
{
private Random rnd = new Random();
private Upychacz pakowacz;
private int zadanaPojemnoscStatku;
private int zadanaLiczbaRodzin;
private List<Rodzina> listaRodzinDoWejscia;
private List<Rodzina> listaRodzinNaPokladzie;
private List<Rodzina> listaRodzinaPozostawionych;
private BindingSource bs_RodzinWej = new BindingSource();
private BindingSource bs_RodzinNaPokladzie = new BindingSource();
private BindingSource bs_RodzinPozostawionych = new BindingSource();
public Form1()
{
InitializeComponent();
listaRodzinDoWejscia = new List<Rodzina>();
listaRodzinNaPokladzie = new List<Rodzina>();
listaRodzinaPozostawionych = new List<Rodzina>();
bs_RodzinWej.DataSource = listaRodzinDoWejscia;
}
private void btn_GenerujRodziny_Click(object sender, EventArgs e)
{
WyczyscStanAplikacji();
int.TryParse(txtB_rodzinDoWejscia.Text, out zadanaLiczbaRodzin);
for (int i = 0; i < zadanaLiczbaRodzin; i++)
listaRodzinDoWejscia.Add(new Rodzina(rnd.Next(2,9)));
WyswietlPodsumowanieRodzinNaWejsciu();
}
private void WyswietlPodsumowanieRodzinNaWejsciu()
{
lBox_RodzinyWPorcie.DataSource = bs_RodzinWej;
bs_RodzinWej.ResetBindings(false);
int liczbaOsob = 0;
foreach (var item in listaRodzinDoWejscia)
liczbaOsob += item.LiczbaOsobWRodzinie;
lbl_OsobDoWejscia.Text = $"Łącznie {liczbaOsob} osób.";
}
private void btn_UstalPojemnoscstatku_Click(object sender, EventArgs e)
{
int.TryParse(txtB_PojemnoscStatku.Text, out zadanaPojemnoscStatku);
label1.Text = $"Pojemnosc Statku: {zadanaPojemnoscStatku}osób";
}
private void btn_ZapakujNaStatek_Click(object sender, EventArgs e)
{
pakowacz = new Upychacz(zadanaPojemnoscStatku, listaRodzinDoWejscia);
listaRodzinNaPokladzie = pakowacz.Zapakowani.OrderBy((x) => x.Nazwa).ToList();
listaRodzinaPozostawionych = pakowacz.Pozostawieni.OrderBy((x) => x.Nazwa).ToList();
WyswietlPodsumowanieZapakowania();
}
private void WyswietlPodsumowanieZapakowania()
{
bs_RodzinNaPokladzie.DataSource = listaRodzinNaPokladzie;
lBox_RodzinyNaStatku.DataSource = bs_RodzinNaPokladzie;
bs_RodzinNaPokladzie.ResetBindings(false);
int osobNaPokladzie = 0;
foreach (var item in listaRodzinNaPokladzie)
osobNaPokladzie += item.LiczbaOsobWRodzinie;
lbl_OsobNaStatku.Text = $"Łącznie {osobNaPokladzie} osob na statku.";
bs_RodzinPozostawionych.DataSource = listaRodzinaPozostawionych;
lBox_RodzinyKtoreNieWeszly.DataSource = bs_RodzinPozostawionych;
bs_RodzinPozostawionych.ResetBindings(false);
int osobPozostawionych = 0;
foreach (var item in listaRodzinaPozostawionych)
osobPozostawionych += item.LiczbaOsobWRodzinie;
lbl_OsobPozostawionych.Text = $"Nie weszło łącznie {osobPozostawionych} osób.";
}
private void WyczyscStanAplikacji()
{
listaRodzinDoWejscia.Clear();
lbl_OsobDoWejscia.Text = $"Łącznie X osób.";
listaRodzinaPozostawionych.Clear();
lbl_OsobPozostawionych.Text = $"Nie weszło łącznie X osób.";
listaRodzinNaPokladzie.Clear();
lbl_OsobNaStatku.Text = $"Łącznie X osob na statku.";
WyswietlPodsumowanieZapakowania();
}
obiekt "Rodzina": implementacja "IComparable" jest po to bo juz podchodzilem do linq ;)
public class Rodzina : IComparable
{
public string Nazwa { get; private set; }
public int LiczbaOsobWRodzinie { get; private set; }
public Rodzina(int liczbaOsob)
{
LiczbaOsobWRodzinie = liczbaOsob;
Nazwa = NazywaczRodzin.NazwijRodzine(liczbaOsob);
}
public Rodzina(string nazwisko, int liczba)
{
this.Nazwa = nazwisko;
this.LiczbaOsobWRodzinie = liczba;
}
public override string ToString()
{
return Nazwa;
}
public int CompareTo(object obj)
{
Rodzina rodz = obj as Rodzina;
if (rodz!=null)
return this.LiczbaOsobWRodzinie.CompareTo(rodz.LiczbaOsobWRodzinie);
else
throw new Exception("Błąd Rodzina: linia: 31");
}
}
obiekt "Upychacz": tutaj robie kopie rodziny do upchania, bo z niej podbieram, docelowo bede z niej korzystal jako buforu do zamieniania miejscami rodzin
public class Upychacz
{
private int dostepnaPojemnosc;
private List<Rodzina> rodzinyDoZapakowania = new List<Rodzina>();
public Upychacz(int zadanaPojemnosc, List<Rodzina> rodzinyDoUpchania)
{
dostepnaPojemnosc = zadanaPojemnosc;
foreach (var item in rodzinyDoUpchania)
{
rodzinyDoZapakowania.Add(new Rodzina(item.Nazwa, item.LiczbaOsobWRodzinie));
}
Zapakowani = new List<Rodzina>();
Pozostawieni = new List<Rodzina>();
PakujTowarzystwo();
}
public List<Rodzina> Zapakowani { get; private set; }
public List<Rodzina> Pozostawieni { get; set; }
public void PakujTowarzystwo()
{
//To miejsce na osadzenie algorytmu pakujacego
//rodzinyDoZapakowania.Sort();
for (int i = rodzinyDoZapakowania.Count - 1; i >= 0; i--)
{
if (PoliczLudziW(Zapakowani) + rodzinyDoZapakowania[i].LiczbaOsobWRodzinie < dostepnaPojemnosc)
{
Zapakowani.Add(rodzinyDoZapakowania[i]);
rodzinyDoZapakowania.RemoveAt(i);
}
else
{
Pozostawieni.Add(rodzinyDoZapakowania[i]);
rodzinyDoZapakowania.RemoveAt(i);
}
}
}
private int LiczbaWolnychMiejscNaStatku()
{
return dostepnaPojemnosc - PoliczLudziW(Zapakowani);
}
private int PoliczLudziW(List<Rodzina> kolekcjaRodzin)
{
int wynik = 0;
foreach (Rodzina item in kolekcjaRodzin)
wynik += item.LiczbaOsobWRodzinie;
return wynik;
}
}
i "nazywacz rodzin":
public static class NazywaczRodzin
{
private static int licznikNazw = 0;
private static int surfiks = 1;
private static char[] literki = new char[] { 'A', 'B', 'C', 'D', 'E',
'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O',
'P', 'Q', 'R', 'S', 'T',
'U', 'W', 'X', 'Y', 'Z' };
public static string NazwijRodzine(int licznosc)
{
string nazwiskoRodziny =
$"Rodzina-{literki[licznikNazw].ToString()}{((surfiks != 1) ? surfiks.ToString() : "" )}__{licznosc}osobowa";
if (licznikNazw % 24 == 0 && licznikNazw != 0)
{
surfiks++;
licznikNazw = -1;
}
licznikNazw++;
return nazwiskoRodziny;
}
}