Zadanie do sprawdzenia- problem plecakowy

Odpowiedz Nowy wątek
2017-05-22 19:38

Rejestracja: 2 lata temu

Ostatnio: 2 lata temu

0

Jest takie zadanie "W budynku mieszkalnym znajduje się winda, której maksymalne obciążenie to 900 kg. Z windy chce skorzystać pewnia liczba osób, w tym:

  • 2 osoby o wadze 52 kg i wzroście 160 cm
  • 1 osoba o wadze 52 kg i wzroście 158 cm
  • 4 osoby o wadze 27 kg i wzroście 125 cm
  • 2 osoby o wadze 102 kg i wzroście 180 cm
  • 4 osoby o wadze 78 kg i wzroście 172 cm
  • 3 osoby o wadze 64 kg i wzroście 160 cm
  • 2 osoby o wadze 64 kg i wzroście 170 cm
  • 3 osoby o wadze 47 kg i wzroście 150 cm
  • 4 osoby o wadze 92 kg i wzroście 179 cm
    Ile osób i o jakiej wadze powinno wsiąść do windy w pierwszej kolejności, aby całkowita suma ich wysokości (czyli wzrostu) była największa? Podaj specyfikację zadania oraz zaproponuj algorytm rozwiązujący ten problem metodą zachłanną i zapisz go w postaci programu."

A to mój program:

using namespace std;

int main()
{

    int wagawindy=900;

    int wagi[25]= {52,52,52,27,27,27,27,102,102,78,78,78,78,64,64,64,64,64,47,47,47,92,92,92,92};
    int wzrost[25]= {160,160,158,125,125,125,125,180,180,172,172,172,172,160,160,160,170,170,150,150,150,179,179,179,179};

    float proporcje[25];
    for(int i=0; i<25; i++) proporcje[i]=wzrost[i]/wagi[i];

    int zamiana;
    do
    {
        zamiana=0;
        for (int i=0; i<25; i++)
        {
            if (proporcje[i]>proporcje[i+1])
            {
                zamiana=zamiana+1;
                swap(proporcje[i],proporcje[i+1]);
                swap(wagi[i],wagi[i+1]);
                swap(wzrost[i],wzrost[i+1]);
            }
        }
    }
    while(zamiana!=0);
    cout<<" do windy zmieści się osoba o: ";
    for(int k=0; k<25; k++)
        if(wagi[k]<wagawindy)
        {
            wagawindy-=wagi[k];
            cout<<"wadze"<<wagi[k]<<" i "<<"wzroscie"<<wzrost[k]<<endl;

        };

    return 0;
}

`

Czy dobrze zrobiłam to zadanie? Możnaby to zrobić jakoś prościej?

Pozostało 580 znaków

2017-05-22 20:59

Rejestracja: 5 lat temu

Ostatnio: 11 godzin temu

Lokalizacja: Szczecin

0

masz zastosować bruteforce, czyli sprawdzić wszystkie przypadki i wypisać najwyższą sumę wzrostu;

ja bym tutaj zastosował rekurencję

edit:
napisałem to u siebie bez rekurencji, rzeczywiście to jest overkill;

wystarcza 2 pętle

edytowany 1x, ostatnio: gośćabc, 2017-05-22 21:19
Ale przecież w poleceniu jest napisane, żeby zastosować metodę zachłanną, a nie bruteforce. - itroitz 2017-05-22 21:19
a co to jest metoda zachłanna? nie operuję po polsku, myślałem że to bruteforce - gośćabc 2017-05-22 21:20
greedy algorithm - itroitz 2017-05-22 21:22
aa ok, no to teraz to się wydaje proste - gośćabc 2017-05-22 21:24

Pozostało 580 znaków

2017-05-22 21:15

Rejestracja: 2 lata temu

Ostatnio: 2 lata temu

0

A od czego można tu zastoswać rekurencje? O.o

Pozostało 580 znaków

2017-05-22 21:16

Rejestracja: 2 lata temu

Ostatnio: 2 dni temu

0

Ale ty nawet tego nie spróbowałaś skompilować?
To sortowanie jest źle napisane, bo dla i = 24 odwołujesz się do proporcje[24+1], co jest poza zakresem tablicy.

edytowany 1x, ostatnio: itroitz, 2017-05-22 21:17
Akurat sortowanie skopiowałam z jakiejś strony z algorytmami, więc w sumie nie spodziewałam się błedów to raz, a dwa to jak skompilowałam to nie było jakichś widocznych błędów tzn( liczb z kosmosu czy coś) - GrumpyFox 2017-05-22 21:19

Pozostało 580 znaków

2017-05-22 21:32

Rejestracja: 5 lat temu

Ostatnio: 11 godzin temu

Lokalizacja: Szczecin

0

i jeszcze zobacz na tę niespodziankę

#include <iostream>
#include <map>
#include <unordered_map>
#include <tuple>
#include <set>
#include <sstream>
#include <vector>
#include <algorithm>
#include <thread>
#include <chrono>
#include <ctime>
#include <functional>

int main()
{
    int const size = 3;
    std::array<int, size> weight { 3, 7, 8 };
    std::array<int, size> height { 10, 20, 30 };
    std::array<double, size> prop;

    for(int i = 0 ; i < size ; ++i) {
        prop[i] = height[i] / weight[i];
    }

    for(auto e : prop) {
        std::cout << e;
    }

    return 0;
}

https://wandbox.org/permlink/KloZyGaFAcKJ1ZnJ

w ogóle nie sprawdziłaś jak to działa

edytowany 3x, ostatnio: gośćabc, 2017-05-22 21:36

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0