Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > С/С++
Перезагрузить страницу Задача о рюкзаке
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
GoldShady2000 GoldShady2000 вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.06.2019
По умолчанию Задача о рюкзаке - 25.06.2019, 18:58

Написать решение задачи о рюкзаке. Ёмкость рюкзака 25 кг. 12 предметов.
Ценность и вес задать случайно от 1 до 8.
Сформировать максимально ценный рюкзак.
Один предмет можно брать один раз.
Все этапы работы программы выводить в консоль.

ВОТ МОЙ КОД, НО ОН НЕ ЯВЛЯЕТСЯ ОПТИМАЛЬНЫМ РЕШЕНИЕМ
НУЖНО СОЗДАТЬ ОДИН МАССИВ, ИЛИ ЦИКЛ.
ЧТО БЫ БРАЛИСЬ ВСЕ ПРЕДМЕТЫ!
ПОМОГИТЕ ПОЖАЛУЙСТА! ПРОГРАММА РАБОТАЕТ, НО НУЖНО ДОПОЛНИТЬ!!!


#include "pch.h"
#include <iostream>
#include <time.h>
#include<stdlib.h>
using namespace std;
void Predmet(float P[12], float V[12], float PV[12]) // заполнение массива предметов
{
int x, y, z;
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);
}
Ответить с цитированием
  (#2 (permalink)) Старый
Southpaw Southpaw вне форума
Member
 
Сообщений: 58
Сказал(а) спасибо: 0
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 20.05.2019
По умолчанию 26.06.2019, 08:53

Перечислите все предметы, а я их опишу стихами.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача о рюкзаке Alex1878 Prolog 1 02.12.2015 22:33
исправить ошибки в задаче о рюкзаке Lowrayder С/С++ 1 28.12.2012 17:18
задача о рюкзаке(ранце) в DevCpp Lowrayder Задания за деньги 2 12.10.2012 18:56
Динамическое программирование, Visual C#/C++, задача о рюкзаке fanpilot Вопросы начинающих программистов 0 22.12.2011 00:56
Помогите, задача по прологу, срочно...задача с высказываниями 4ixOn Prolog 6 10.07.2011 23:29
Помогите, задача по прологу, срочно...задача о станках 4ixOn Prolog 3 09.07.2011 22:48
Задача по MPI 45$ Naikon1988 Задания за деньги 2 22.12.2010 18:12
Усложнённая формулировка "Задачи о рюкзаке" Geddricko Алгоритмы 3 10.12.2010 02:46
Задача о рюкзаке методом ДП ClA Pascal 4 25.08.2009 14:58
Задача Yunno Pascal 4 11.10.2008 19:11
задача на Си int33 Задания за деньги 1 14.04.2006 17:53



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов