Найти оптимальную сборку по типу домов для получения наибольшего количества квартир

@balky02 · 02.09.2016, 14:55. **Показов** 2133. **Ответов** 6

Студворк — интернет-сервис помощи студентам

Всем привет!
Помогите, пожалуйста, с решением задачи ниже.

Условия
Из строительных деталей четырёх видов можно собрать четыре типа домов. Для сборки необходимо деталей:
__________________________________Виды деталей_______________
______________________1-й вид____2-й вид ____3-й вид ____4-й вид
10‐квартирный дом________60________90_________30______ ___50
15‐квартирный дом________95________131_________20_____ ____60
20‐квартирный дом________110_______172_________60_____ ____45
25‐квартирный дом________134________195_________70____ _____75
Всего имеется 850 деталей первого, 1250 деталей второго, 500 деталей третьего и 720 деталей четвёртого вида.

Сколько и каких домов нужно собрать, чтобы общее количество квартир в них было наибольшим?

@golatin · 02.09.2016, 15:50

Иными словами:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}60{x}_{1}+95{x}_{2}+110{x}_{3}+134{x}_{4}\leq 850 \\ 90{x}_{1}+13{x}_{2}+172{x}_{3}+195{x}_{4}\leq 1250\\ 30{x}_{1}+20{x}_{2}+60{x}_{3}+70{x}_{4}\leq 500\\ 50{x}_{1}+60{x}_{2}+45{x}_{3}+75{x}_{4}\leq 720\end{matrix}\right.$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F({x}_{1},{x}_{2},{x}_{3},{x}_{4})=10{x}_{1}+15{x}_{2}+20{x}_{3}+25{x}_{4}\rightarrow \max \\$

симплекс-метод дает:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{1}=0,{x}_{2}=0,{x}_{3}=0,{x}_{4}=6\frac{23}{67}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F(0,0,0,6\frac{23}{67})=10*0 + 15*0 + 20*0 + 25*6\frac{23}{67}=158\frac{39}{67}$ квартиры.

Но если дома могут быть лишь целыми

, то метод ветвей и границ дает:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{1}=1,{x}_{2}=0,{x}_{3}=1,{x}_{4}=5$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F(1,0,1,5)=10*1 + 15*0 + 20*1 + 25*5=155$ квартиры.

Не по теме:

гуглите "метод ветвей и границ" + "python" и будет вам счастье...

@balky02 · 03.09.2016, 10:50 **[ТС]**

Не по теме:

Сообщение от golatin

гуглите "метод ветвей и границ" + "python" и будет вам счастье...

golatin!
Образно как бы попросил перевести фразу с русского на французский (Python). Если бы интересовал интернациональный язык — математика, то обратился сразу по профилю, туда https://www.cyberforum.ru/mathematics/

Добавлено через 18 часов 38 минут
Помогите, пожалуйста, перевести код с Haskell на Python.

Вводим код для целочисленного перебора:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
m10 = minimum [850 `div` 60, 1250 `div` 90, 500 `div` 30, 720 `div` 50]
m15 = minimum [850 `div` 95, 1250 `div` 131, 500 `div` 20, 720 `div` 60] 
m20 = minimum [850 `div` 110, 1250 `div` 172, 500 `div` 60, 720 `div` 45]
m25 = minimum [850 `div` 134, 1250 `div` 195, 500 `div` 70, 720 `div` 75]
 
task = filter (\ x -> fst x == fmax) flst 
     where fmax = maximum $ map fst flst
           flst = zip (map fs lst) lst
           lst  = [(n10,n15,n20,n25)| n10 <- [0,1..m10], 
                                  n15 <- [0,1..m15], 
                                  n20 <- [0,1..m20],
                                  n25 <- [0,1..m25],
                                  n10*60+n15*95+n20*110+n25*134 <= 850,
                                  n10*90+n15*131+n20*172+n25*195 <= 1250,
                                  n10*30+n15*20+n20*60+n25*70 <= 500,
                                  n10*50+n15*60+n20*45+n25*75 <= 720]
           fs (x,y,z,k) = 10*x+15*y+20*z+25*k

Ответ:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
GHCi, version 8.0.1: [url]http://www.haskell.org/ghc/[/url]  :? for help
Prelude> :cd C:\Users\admin\Documents\MyHaskell
Prelude> :load "MyHask6.hs"
[1 of 1] Compiling Main             ( MyHask6.hs, interpreted )
 
MyHask6.hs:12:1: warning: [-Wtabs]
    Tab character found here, and in 31 further locations.
    Please use spaces instead.
Ok, modules loaded: Main.
*Main> task
[(155,(1,0,1,5)),(155,(3,0,0,5))]
*Main>

@shsv · 03.09.2016, 19:09

Почти буквальный "перевод"

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
total_parts = [850, 1250, 500, 720]
bld10 = [60, 90, 30, 50]
bld15 = [95, 131, 20, 60]
bld20 = [110, 172, 60, 45]
bld25 = [134, 195, 70, 75]
 
 
div = lambda a, b: a // b
fs = lambda x: 10*x[0] + 15*x[1] + 20*x[2] + 25*x[3]
 
m10 = min(map(div, total_parts, bld10))
m15 = min(map(div, total_parts, bld15))
m20 = min(map(div, total_parts, bld20))
m25 = min(map(div, total_parts, bld25))
 
lst = [(n10, n15, n20, n25) for n10 in range(m10 + 1)
                            for n15 in range(m15 + 1)
                            for n20 in range(m20 + 1)
                            for n25 in range(m25 + 1)
                            if n10*bld10[0] + n15*bld15[0] + n20*bld20[0] + n25*bld25[0] <= total_parts[0] and
                               n10*bld10[1] + n15*bld15[1] + n20*bld20[1] + n25*bld25[1] <= total_parts[1] and
                               n10*bld10[2] + n15*bld15[2] + n20*bld20[2] + n25*bld25[2] <= total_parts[2] and
                               n10*bld10[3] + n15*bld15[3] + n20*bld20[3] + n25*bld25[3] <= total_parts[3]]
flst = zip(map(fs, lst), lst)
fmax = max(map(fs, lst))
 
res = [it for it in flst if it[0] == fmax]
 
print(res)

@balky02 · 03.09.2016, 20:24 **[ТС]**

Сообщение от shsv

Почти буквальный "перевод"

shsv!
Отлично! Спасибо, Вы умница!!

Python
1
2
3
4
*** Python 3.4.4 (v3.4.4:737efcadf5a6, Dec 20 2015, 19:28:18) [MSC v.1600 32 bit (Intel)] on win32. ***
>>> 
[(155, (1, 0, 1, 5)), (155, (3, 0, 0, 5))]
>>>

shsv! Помогите, пожалуйста, чтобы Haskell написал дополнительную информацию.
Предполагаем: в ходе решения могут оказаться равные результаты количества квартир, тогда дополнительным критерием выступает экономия деталей, которая определяет лучший вариант.
Пусть изначально количество деталей:
D1 = 850; D2 = 1250; D3 = 500; D1 = 720.
При равных вариантах: 155 = 155, подсчитываем вручную, нерационально:
1) Для первого (155,(1,0,1,5))
d1 = D1 – R1 = 850 – (1*60 + 1*110 + 5*134) = 850 – 840 = 10
d2 = D2 – R2 = 1250 – (1*90 + 1*172 + 5*195) = 1250 – 1237= 13
d3 = D3 – R3 = 500 – (1*30 + 1*60 + 5*70) = 500 – 440 = 60
d4 = D4 – R4 = 720 – (1*50 + 1*45 + 5*75) = 720 – 470 = 250
10 + 13 + 60+ 250 = 333
Надо чтобы он пояснил, примерно так: [(155,(1,0,1,5)) material_rests (333,(10,13,60,250))]

2) Для второго (155,(3,0,0,5))
d1 = D1 – R1 = 850 – (3*60 + 5*134) = 850 – 850 = 0
d2 = D2 – R2 = 1250 – (3*90 + 5*195) = 1250 – 1245 = 5
d3 = D3 – R3 = 500 – (3*30 + 5*70) = 500 – 440 = 60
d4 = D4 – R4 = 720 – (3*50 + 5*75) = 720 – 525 = 195
0 + 5 + 60 + 195 = 260
Примерно так: [(155,(3,0,0,5)) material_rests (260,(0,5,60,195))]

Мы дальше сами легко определим, что первый вариант больше добра (деталей) сэкономил — значит, он лучший.

Можете не обращать внимания на "мою писанину". Сделайте, как получится!
Важно только: сделать ещё хоть маленький шажок вперёд — любым способом.

@shsv · 04.09.2016, 10:21

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from itertools import groupby
 
total_parts = [850, 1250, 500, 720]
bld10 = [60, 90, 30, 50]
bld15 = [95, 131, 20, 60]
bld20 = [110, 172, 60, 45]
bld25 = [134, 195, 70, 75]
 
 
div = lambda a, b: a // b
fs = lambda x: 10*x[0] + 15*x[1] + 20*x[2] + 25*x[3]
d1 = lambda n0, n1, n2, n3: total_parts[0] - (n0*bld10[0] + n1*bld15[0] + n2*bld20[0] + n3*bld25[0])
d2 = lambda n0, n1, n2, n3: total_parts[1] - (n0*bld10[1] + n1*bld15[1] + n2*bld20[1] + n3*bld25[1])
d3 = lambda n0, n1, n2, n3: total_parts[2] - (n0*bld10[2] + n1*bld15[2] + n2*bld20[2] + n3*bld25[2])
d4 = lambda n0, n1, n2, n3: total_parts[3] - (n0*bld10[3] + n1*bld15[3] + n2*bld20[3] + n3*bld25[3])
 
m10 = min(map(div, total_parts, bld10))
m15 = min(map(div, total_parts, bld15))
m20 = min(map(div, total_parts, bld20))
m25 = min(map(div, total_parts, bld25))
 
lst = [(n10, n15, n20, n25) for n10 in range(m10 + 1)
                            for n15 in range(m15 + 1)
                            for n20 in range(m20 + 1)
                            for n25 in range(m25 + 1)
                            if d1(n10, n15, n20, n25) >= 0 and
                               d2(n10, n15, n20, n25) >= 0 and
                               d3(n10, n15, n20, n25) >= 0 and
                               d4(n10, n15, n20, n25) >= 0]
flst = zip(map(fs, lst), lst)
fmax = max(map(fs, lst))
 
res = [it for it in flst if it[0] == fmax]
 
print(res)
 
 
if len(res) > 1:
    rests = lambda x: d1(*x[1]) + d2(*x[1]) + d3(*x[1]) + d4(*x[1])
    # оптимальное решение
    key, grp = next(groupby(sorted(res, key=rests, reverse=True), key=rests))
    for it in grp:
        fs, rs = it
        print('{}, {} material_rests {}, ({}, {}, {}, {})'.format(
                    fs, rs, key, d1(*rs), d2(*rs), d3(*rs), d4(*rs)))
 
 
#     # все решения
#     print('-'*60)
#     for x in sorted(res, key=rests, reverse=True):
#         print('{}, {} material_rests {}, ({}, {}, {}, {})'.format(
#                     x[0], x[1], rests(x), d1(*x[1]), d2(*x[1]), d3(*x[1]), d4(*x[1])))

@balky02 · 04.09.2016, 11:32 **[ТС]**

Сообщение от shsv

from itertools import groupby

shsv!
Спасибо!! Нет слов, гениально!

Вы наверно профессиональный программист, профессор.

Код с дополнением, включая Библиотеку:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from itertools import groupby
 
total_parts = [850, 1250, 500, 720]
bld10 = [60, 90, 30, 50]
bld15 = [95, 131, 20, 60]
bld20 = [110, 172, 60, 45]
bld25 = [134, 195, 70, 75]
 
 
div = lambda a, b: a // b
fs = lambda x: 10*x[0] + 15*x[1] + 20*x[2] + 25*x[3]
d1 = lambda n0, n1, n2, n3: total_parts[0] - (n0*bld10[0] + n1*bld15[0] + n2*bld20[0] + n3*bld25[0])
d2 = lambda n0, n1, n2, n3: total_parts[1] - (n0*bld10[1] + n1*bld15[1] + n2*bld20[1] + n3*bld25[1])
d3 = lambda n0, n1, n2, n3: total_parts[2] - (n0*bld10[2] + n1*bld15[2] + n2*bld20[2] + n3*bld25[2])
d4 = lambda n0, n1, n2, n3: total_parts[3] - (n0*bld10[3] + n1*bld15[3] + n2*bld20[3] + n3*bld25[3])
 
m10 = min(map(div, total_parts, bld10))
m15 = min(map(div, total_parts, bld15))
m20 = min(map(div, total_parts, bld20))
m25 = min(map(div, total_parts, bld25))
 
lst = [(n10, n15, n20, n25) for n10 in range(m10 + 1)
                            for n15 in range(m15 + 1)
                            for n20 in range(m20 + 1)
                            for n25 in range(m25 + 1)
                            if d1(n10, n15, n20, n25) >= 0 and
                               d2(n10, n15, n20, n25) >= 0 and
                               d3(n10, n15, n20, n25) >= 0 and
                               d4(n10, n15, n20, n25) >= 0]
flst = zip(map(fs, lst), lst)
fmax = max(map(fs, lst))
 
res = [it for it in flst if it[0] == fmax]
 
print(res)
 
 
if len(res) > 1:
    rests = lambda x: d1(*x[1]) + d2(*x[1]) + d3(*x[1]) + d4(*x[1])
    # оптимальное решение
    key, grp = next(groupby(sorted(res, key=rests, reverse=True), key=rests))
    for it in grp:
        fs, rs = it
        print('{}, {} material_rests {}, ({}, {}, {}, {})'.format(
                    fs, rs, key, d1(*rs), d2(*rs), d3(*rs), d4(*rs)))
 
 
#     # все решения
        print('-'*60)
        for x in sorted(res, key=rests, reverse=True):
         print('{}, {} material_rests {}, ({}, {}, {}, {})'.format(
                     x[0], x[1], rests(x), d1(*x[1]), d2(*x[1]), d3(*x[1]), d4(*x[1])))

Ответ, с расшифровкой остатка деталей по оптимальным вариантам.

Python
1
2
3
4
5
6
7
>>> 
[(155, (1, 0, 1, 5)), (155, (3, 0, 0, 5))]
155, (1, 0, 1, 5) material_rests 333, (10, 13, 60, 250)
------------------------------------------------------------
155, (1, 0, 1, 5) material_rests 333, (10, 13, 60, 250)
155, (3, 0, 0, 5) material_rests 260, (0, 5, 60, 195)
>>>

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .

Найти оптимальную сборку по типу домов для получения наибольшего количества квартир

Решение

Решение

@balky02 Заблокирован

	Найти оптимальную сборку по типу домов для получения наибольшего количества квартир 02.09.2016, 14:55. Показов 2133. Ответов 6 Метки нет (Все метки) Всем привет! Помогите, пожалуйста, с решением задачи ниже. Условия Из строительных деталей четырёх видов можно собрать четыре типа домов. Для сборки необходимо деталей: __________________________________Виды деталей_______________ ______________________1-й вид____2-й вид ____3-й вид ____4-й вид 10‐квартирный дом________60________90_________30______ ___50 15‐квартирный дом________95________131_________20_____ ____60 20‐квартирный дом________110_______172_________60_____ ____45 25‐квартирный дом________134________195_________70____ _____75 Всего имеется 850 деталей первого, 1250 деталей второго, 500 деталей третьего и 720 деталей четвёртого вида. Сколько и каких домов нужно собрать, чтобы общее количество квартир в них было наибольшим? 0

@golatin 317 / 268 / 61 Регистрация: 12.10.2011 Сообщений: 434
	02.09.2016, 15:50
	Иными словами: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}60{x}_{1}+95{x}_{2}+110{x}_{3}+134{x}_{4}\leq 850 \\ 90{x}_{1}+13{x}_{2}+172{x}_{3}+195{x}_{4}\leq 1250\\ 30{x}_{1}+20{x}_{2}+60{x}_{3}+70{x}_{4}\leq 500\\ 50{x}_{1}+60{x}_{2}+45{x}_{3}+75{x}_{4}\leq 720\end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?F({x}_{1},{x}_{2},{x}_{3},{x}_{4})=10{x}_{1}+15{x}_{2}+20{x}_{3}+25{x}_{4}\rightarrow \max \\$ симплекс-метод дает: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{1}=0,{x}_{2}=0,{x}_{3}=0,{x}_{4}=6\frac{23}{67}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?F(0,0,0,6\frac{23}{67})=100 + 150 + 200 + 256\frac{23}{67}=158\frac{39}{67}$ квартиры. Но если дома могут быть лишь целыми, то метод ветвей и границ дает: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{1}=1,{x}_{2}=0,{x}_{3}=1,{x}_{4}=5$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?F(1,0,1,5)=101 + 150 + 201 + 255=155$ квартиры. Не по теме: гуглите "метод ветвей и границ" + "python" и будет вам счастье... 3