Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include <vcl.h>
- #include<iostream>
- #pragma hdrstop
- //#pragma argsused
- //предмет -> контейнер -> упаковка (упаковка - это разные вариации контейнеров и предметов, нам надо найти такую, чтобы там было мин.число контейнеров
- const int N=6; // число предметов
- float A[N+1]={0,0.1, 0.2, 0.3, 0.7, 0.8, 0.9}, //размеры предметов
- V[N]; //заполненность контейнеров
- int Box, // кол-во контейнеров в текущей упаковке
- OptBox, //кол-во контейнеров в оптимальной упаковке
- Cont[N], //текущая упаковка
- OptCont[N]; //оптимальная упаковка (ее как раз надо найти)
- void pack(int i)
- { int eps=A[i]*0.1; //некоторое маленькое число (его можно считать = 0)
- for (int j=1; j <= N; j++) { //перебираем контейнеры
- if (V[j]<=eps && (Box+1)>=OptBox) break; // если контейнер j пуст и кол-во контейнеров в текущей упаковке уже превышает оптимальное кол-во, то выходим
- if (j>1&&V[j-1]<=eps) break; //если контейнер не 1 и предыдущий контейнер пустой то выходим
- if (V[j]+A[i]<=1+eps) { //если заполненость контейнера + размер предмета меньше 1 (т.е туда можно положить предмет)
- int B=Box; //в В записываем кол-во кол-во контейнеров в текущей упаковке
- if (V[j]<=eps) Box+=1; // если пустой, то увеличиваем кол-во контейнеров в этой упаковке на 1
- V[j]+=A[i]; //заполняем j контейнер на объем i предмета
- Cont[i]=j; //предмет i помещаем в j контейнер
- if (i<N) pack(i+1); //если текущий предмет не последний, то вызываем рекурсию и пытаемся упаковать след предмет
- else //если нет, то
- {
- OptBox=Box; //в оптим присваиваем текущее кол-во контейнеров в упаковке
- for (int k = 1; k <= N; k++) OptCont[k]=Cont[k]; //в оптимальную упаковку = текущую упаковку
- }
- Box=B; //возвращаем старое старое значение контейнеров в упаковке
- Cont[i]=0; //выкидываем текущий предмет
- V[j]-=A[i]; //вычитаем объем текущего предмета
- }
- }
- }
- int main(int argc, char* argv[])
- {
- for (int i = 1; i <= N; i++) {
- V[i]=0; // все контейнеры очищаем
- Cont[i]=0; //все предметы никуда не помещены (лежат в сторонке)
- OptCont[i]=i; // оптимальное кол-во контейнеров в упаковке = N (тут чуть неуверен)
- }
- OptBox=N; //пока оптимально поместить каждый предмет в свой контейнер)
- Cont[1]=1; //первый предмет упаковываем в 1 вагон
- V[1]=A[1]; // увеличиваем заполненность 1го контейнера на размер 1го предмета
- Box=1; //кол-во контейнеров в текущей упаковке =1
- pack(2); //упаковываем второй предмет
- for (int i = 1; i <= N; i++) std::cout<<OptCont[i]<<" "; //вывод оптимальной упаковки (ответ)
- std::cin.get();std::cin.get();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement