Zadanie do sprawdzenia- problem plecakowy

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?

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

0

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

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.

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

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