Задача №3094. Гирьки: три кучки
Дан набор гирек массой m1, …, mN. Можно ли их разложить на три кучки равной массы?
https://informatics.msk.ru/mod/statements/view.php...
Пока идея 3 мерный массив где dp[i][w1[w2] хранится номер рюкзака если можно с данным индексом составить рюкзаки веса w1 и w2 и -1 я если невозможно составить данные веса но как потом восстановить индексы?
Мой алгоримт пока что
def three_knapsack(a:list):
a.sort(reverse=True)
w=sum(a)
if w%3!=0:
return 1
else:
w=w//3
_dp=[[[ -1 for _ in range(w+2)] for _ in range(w+2)] for _ in range(len(a))]
for i in range(w+1):
for j in range(w+1):
if i==a[0]:
_dp[0][i][j]=1
elif j==a[0]:
_dp[0][i][j]=2
if i==0 and j==0:
_dp[0][i][j]=0
for i in range(len(a)):
_dp[i][0][0]=0
for ii, x in enumerate(a):
if ii==0: continue
for i in range(w+1, -1, -1 ):
for j in range(w+1, -1, -1):
if i>=x and _dp[ii-1][i-x][j]!=-1:
_dp[ii][i][j]=1
elif j>=x and _dp[ii-1][i][j-x]!=-1:
_dp[ii][i][j]=2
elif _dp[ii-1][i][j]!=-1:
_dp[ii][i][j]=0
return any([_dp[x][w][w]>=0 for x in range(len(a))]), _dp
но оня явно не работет - кидает прото в кучу 3
