Я пытаюсь решить следующее с помощью инструментов ИЛИ:
Даны следующие пакеты с шариками разного цвета:
Сколько мешков каждого типа мне понадобится, чтобы иметь одинаковое количество мячей каждого цвета?
Для таких случаев, когда есть точный ответ, следующий код:
bags= [
[10,5,85,0],
[25,50,25,0],
[0,100,0,0],
[90,5,5,0],
[2,0,98,0],
[0,0,0,100]
]
bags_n = len(bags)
color_n = len(bags[0])
print(f'Bags: {bags_n}')
print(f'Colors: {color_n}')
color_count= [0] * color_n
for c in range(color_n):
for b in bags:
color_count[c]+= b[c]
print(color_count)
print(f'Inital total: {sum(color_count)}')
print(f'Inital equal share: {sum(color_count)//color_n}')
model = cp_model.CpModel()
weights = []
for r in range(bags_n):
weights.append(model.NewIntVar(1,1000,f'Weight of Bag: {r}'))
total = model.NewIntVar(0, 100000, 'total')
model.Add(
sum(flatten(
[[bags[r][c] * weights[r] for r in range(bags_n)] for c in range(color_n)]
)) == total
)
equal = model.NewIntVar(0, 10000, 'equal share')
model.AddDivisionEquality(equal, total, color_n)
for c in range(color_n):
diff_c = model.NewIntVar(0, 1000, 'diff_'+str(c))
model.Add(diff_c == sum([bags[r][c] * weights[r] for r in range(bags_n)]) - equal)
model.AddAbsEquality(0, diff_c)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f'Maximum of objective function: {solver.ObjectiveValue()}\n')
for v in weights:
print(f'{solver.Value(v)}')
print(f'total = {solver.Value(total)}')
print(f'equal share = {solver.Value(equal)}')
else:
print(status)
возвращает действительные веса:
82 2 70 78 5 79
Если я изменю настройку на что-то вроде
bags= [
[50,40,10],
[30,20,50],
[30,30,40],
[30,25,45],
]
Я предполагаю, что модель становится невозможной из-за того, что нет весов, удовлетворяющих AbsEquality для каждого цвета.
Как я могу изменить это, чтобы получить решение, наиболее близкое к равномерному распределению, даже если идеальное решение невозможно?
Если вы стремитесь получить максимально равное количество шаров каждого цвета, вы можете создать переменную, которая представляет собой разницу между максимальным количеством шаров любого цвета и минимальным количеством шаров любого цвета, а затем добавить в качестве цели минимизировать эту переменную.
Что касается пресса, вы можете посмотреть github.com/google/or-tools/blob/stable/examples/python/…
Спасибо @ChristopherHamkins! Поправлю и формулировку вопроса.
Только этот последний не очень серьезный комментарий: если бы вы также допустили ноль в качестве количества мешков, вы всегда могли бы получить точное решение, а именно 0 шаров каждого цвета ;-)






Предложение Кристофера Хэмкинса отлично сработало:
bags= [
[50,40,10],
[30,20,50],
[30,30,40],
[30,25,45],
]
bags_n = len(bags)
color_n = len(bags[0])
print(f'Bags: {bags_n}')
print(f'Colors: {color_n}')
color_count= [0] * color_n
for c in range(color_n):
for b in bags:
color_count[c]+= b[c]
print(color_count)
print(["{0:.0%}".format(c/sum(color_count)) for c in color_count])
model = cp_model.CpModel()
weights = []
for r in range(bags_n):
weights.append(model.NewIntVar(1,500,f'Weight of Bag: {r}'))
max = model.NewIntVar(0,100000000,f'Max')
model.AddMaxEquality(max,
[sum([bags[r][c] * weights[r] for r in range(bags_n)]) for c in range(color_n)]
)
min = model.NewIntVar(0,100000000,f'Min')
model.AddMinEquality(min,
[sum([bags[r][c] * weights[r] for r in range(bags_n)]) for c in range(color_n)]
)
diff = model.NewIntVar(0,100000000,f'Diff')
model.Add(max - min == diff)
model.Minimize(diff)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f'max = {solver.Value(max)}')
print(f'min = {solver.Value(min)}')
print(f'diff = {solver.Value(diff)}')
bag_weights = [0] * bags_n
for i,v in enumerate(weights):
bag_weights[i] = solver.Value(v)
print(f'{solver.Value(v)}')
color_count = [0] * color_n
for c in range(color_n):
for i,b in enumerate(bags):
color_count[c]+= (b[c] * bag_weights[i])
print(color_count)
print(["{0:.0%}".format(c/sum(color_count)) for c in color_count])
else:
print(status)
Вы имеете в виду «четное количество» или «равное количество» шаров каждого цвета?