#algorithm #design-patterns
Вопрос:
У меня есть программа, в которой есть несколько продуктов. Они могут быть как простыми, так и состоять из других продуктов, причем те, которые составлены, имеют рецепт с указанием типа и количества каждого компонента. Мне нужно проверить, смогу ли я получить достаточно данного продукта. Если это просто, я могу просто посмотреть, достаточно ли у меня единиц, но если он составлен, мне нужно посмотреть, смогу ли я создать достаточное количество копий с остальных продуктов. Проблема в том, что я не могу просто попытаться применить составной шаблон, потому что компоненты могут быть составлены и иметь общие продукты. Итак, для иллюстрации представьте, что я хочу посмотреть, хватит ли у меня материалов для сборки 4 автомобилей. Проблема будет заключаться в следующем:
Car:
4 tires
1 wheel
1 chassis
Tire:
2 rubber
Wheel:
4 rubber
Chassis:
10 metal
**Available**
2 Cars
3 Tires
0 Wheels
40 Metal
12 Rubber
С помощью этого я могу получить только три автомобиля (2 1), однако, если я проверил по компонентам, у меня было достаточно каждого материала, чтобы собрать каждый из компонентов для четырех автомобилей. Какова будет структура функций, которые мне нужно реализовать?
Комментарии:
1. Был бы самый простой способ «сгладить» проблему? Поэтому для каждого компонента вы вычисляете, сколько требуется сырья. Автомобиль-это (резина 4х2 резина 1х4 металл 1х10 =) 12 резиновых и 10 металлических. Затем вы также выравниваете доступные вам материалы, «разлагая» композиты, так что у вас есть (резина 2×12 металл 2×10 резина 3×2 40 металлов 12 каучуков =) 42 каучука и 60 металлов. Теперь вы можете просто рассчитать, сколько автомобилей вы можете произвести на сырье, и взять минимум.
2. Ладно, да, это может быть решением. Я также подумал о том, чтобы, возможно, сделать копию базы данных и начать удалять компоненты из копии, проверяя, не закончились ли у меня что-то, но это решение определенно кажется лучшим
3. Полное устранение проблемы, по-видимому, даст вам больше свободы, чем у вас есть на самом деле, хотя. Для автомобиля требуется всего 12 резин, но вы не можете взять эти 12 резин с 3 колес, так как на каждый автомобиль приходится не более 1 колеса.
4. Идея алгоритма: Ведите учет всех имеющихся у вас материалов. Попытайтесь сделать автомобиль, взяв необходимое количество шин, колес и шасси в количестве материалов. Если это возможно, то увеличьте количество автомобилей на 1 и уменьшите все соответствующие материалы. Если шина отсутствует, попробуйте изготовить шину, взяв необходимое количество материалов; то же самое касается колеса и шасси. Продолжайте двигаться до тех пор, пока вы успешно не создадите автомобиль или вам не удастся создать автомобиль. Если вам это удалось, сделайте петлю, чтобы сделать вторую машину.