Здравствуйте и спасибо за помощь!
Итак, у нас есть список фейерверков, содержащий
1) Количество в наличии
2) Количество фейерверков в этом пакете
3) Диаметр, равный шуму, и
4) Цена.
Это список:
25 17 10 21
10 15 10 18
5 16 10 19
10 15 12 20
15 9 11 12
10 7 28 23
8 7 16 11
10 6 16 10
25 10 18 25
25 12 18 27
10 5 40 35
60 40 5 27
525 30 90
50 1 60 8
Наша задача - создать список покупок и купить фейерверк, чтобы получить максимально возможный шум.У нас есть рюкзак вместимостью 1000 €.Мы также должны решить эту проблему без использования таблиц (то есть с динамическим программированием).
Я использую только один класс с именем Package, который содержит четыре ограничения, как показано выше.
Сначала яЯ подумал, что имеет смысл попытаться написать алгоритм для обычного ранца, так что просто с ценой и диаметром (= вес).Я проверил это с другим списком, и он работал отлично.Я просто перебрал все пакеты, а затем снова использовал вложенный цикл for, чтобы найти лучшее созвездие (исчерпывающий поиск).Моя следующая идея состояла в том, чтобы объединить количество фейерверков на упаковку с диаметром, потому что фейерверк можно купить только в полной упаковке.
Единственное, что я до сих пор не выяснил, это что делать с количеством упаковок на складе.Мол, с моим текущим алгоритмом он просто покупает все пакеты фейерверков, пока рюкзак не заполнится.Но очевидно, что это не будет правильно.
void knapsack(vector<Package*> stock){
vector<int> indices, tmp_indices;
int noise,tmp_noise= 0;
int price;
for (unsigned int i = 0; i < stock.size(); i++) {
price = stock[i]->price;
noise = stock[i]->diameter*stock[i]->number_fireworks;
indices.push_back(i);
for (unsigned int j = 0; j < stock.size(); j++) {
if (i != j) {
if (price+stock[j]->price<= BUDGET) {
price+=stock[j]->price;
noise+=stock[j]->diameter*stock[j]->number_fireworks;
indices.push_back(j);
}
}
}
// After second loop we have a new possible constellation
// Check if the previous constellation had a lower value and if so, set it to the current one
if (noise > tmp_noise) {
tmp_noise = noise;
tmp_indices.clear();
// tmp save
for (auto &index : indices) {
tmp_indices.push_back(index);
}
}
price= 0;
noise = 0;
indices.clear();
}
// Best constellation found, Print the shopping list
cout << "\Stock.\tNum\Diameter.\Price\n" << endl;
for(unsigned int i = 0; i < tmp_indices.size(); i++) {
cout << stock[tmp_indices[i]]->stock<< "\t";
cout << stock[tmp_indices[i]]->number_fireworks<< "\t";
cout << stock[tmp_indices[i]]->diameter<< "\t";
cout << stock[tmp_indices[i]]->price<< "\t\n";
}
}
Нам сказали, что мы должны быть в состоянии потратить ровно 1000 €, чтобы получить правильное сочетание фейерверков.Моя идея состояла в том, чтобы добавить еще один цикл for для перебора количества доступных пакетов, но это не сработало ...
Это был наш первый урок, и я немного отчаялся, потому что у нас есть толькоузнал, как решить проблему ранца с двумя ограничениями и с помощью таблицы R.
Редактировать: Поскольку один пользователь настаивал на получении конкретного вопроса, вот он: Идея использования другого цикла для включения третьегоограничение корректно или есть лучший / более простой способ сделать это?Или возможно, что мне нужен совершенно другой подход для рюкзака с 3 вместо 2 ограничений?
Заранее спасибо за помощь