Top.Mail.Ru
Ответы

Помогите, пожалуйста, исправить жадный алгоритм о рюкзаке

Не наполняет рюкзак элементами полностью
Отсортированный список предметов:
Цена Вес Уд. цен.
7 4 1.75
5 4 1.25
7 6 1.16667
5 5 1
3 4 0.75
3 5 0.6
3 5 0.6
3 6 0.5
1 2 0.5
3 8 0.375
2 8 0.25
1 7 0.142857
Ответ:
Цена Вес Уд. цен.
7 4 1.75
5 4 1.25
7 6 1.16667
5 5 1
3 4 0.75
тут, к примеру, есть элемент с весом 2, а он игнорируется

#include <stdio.h>
#include "Windows.h"
#include <algorithm>
#include <iostream>

using namespace std;

void Predmet(float P[12], float V[12], float PV[12]) // заполнение массива предметов
{
int x;
for (x = 0; x < 12; x++)
{
P[x] = rand() % 8 + 1; // ценность предмета
V[x] = rand() % 8 + 1; // Вес предмета
PV[x] = P[x] / V[x]; // Удельная ценность предмета
}
}

void Vivod(float* P, float* V, float* PV, int N)
{
int x;
cout << endl << "Цена\t" << "Вес\t" << "Уд. цен." << endl;
for (x = 0; x < N; x++)
{
cout << P[x] << "\t" << V[x] << "\t" << PV[x] << endl;
}
}

void Greedy(float P[12], float V[12], float PV[12], int N, float Emk) // жадный алгоритм
{
int x, y, k = 0; // k - кол-во предметов
float buf1, buf2, buf3, SumV = 0, SumP = 0;
for (x = 0; x < N - 1; x++)
for (y = x + 1; y < N; y++)
{
if (PV[x] < PV[y] || PV[x] == PV[y] && V[x] < V[y])
{
buf1 = P[x];
P[x] = P[y];
P[y] = buf1;

buf2 = V[x];
V[x] = V[y];
V[y] = buf2;

buf3 = PV[x];
PV[x] = PV[y];
PV[y] = buf3;

}
}
cout << "Отсортированный список предметов:";
Vivod(P, V, PV, N);
for (x = 0; x < N; x++)
{
if (SumV + V[x] <= Emk)
{
SumV += V[x];
SumP += P[x];
k++;
}
else break;
}
for (y = 0; y < N; y++)
{
if (SumV + V[y] <= Emk)
{
SumV += V[y];
SumP += P[y];
k++;
}
else break;
}
cout << "Ответ:";
Vivod(P, V, PV, k);
cout << "Кол-во предметов: " << k << endl << "Общий вес предметов: " << SumV << endl << "Общая ценность " << SumP;
}

int main()
{
float Ves[12], Price[12], UdPr[12]; // Price - ценность предмета Ves - вес предмета UdPr - удельная ценность
setlocale(LC_ALL, "Russian");
srand(time(NULL));
Predmet(Price, Ves, UdPr);
cout << "Список предметов:";
Vivod(Price, Ves, UdPr, 12);
Greedy(Price, Ves, UdPr, 12, 25);
}

По дате
По рейтингу
Аватар пользователя
Новичок

Дело в том, что жадный алгоритм является приближённым и поэтому не гарантирует оптимального решения. А сам алгоритм запрограммирован верно.

Аватар пользователя
Мудрец

Я никогда раньше такой алгоритм не встречал.
Но если судить по названию, то в жадный рюкзак пихают вещи подороже да побольше, сколько влезет.
В жадной функции сначала идёт сортировка по удельной цене. То есть, по наиболее дорогому материалу.
Второй критерий сортировки -- количество.
И поэтому в рюкзак кладётся не всё.
А только то, что влезло.