Задать вопрос
@alex_agaphe

Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

Задача №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
  • Вопрос задан
  • 109 просмотров
Подписаться 1 Простой 10 комментариев
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Для восстановления вам нужен второй массив, где вы храните одно из 3 значений - в какой из трех наборов идет i-ая гиря. Когда считаете dp и пишите, что можно составить i, w1, w2 вы же эти значения получили куда-то поместив последний элемент. У вас или к w1 что-то было прибавлено, или к w2, или никуда. Это 3 варианта.

При восстановлении начните с N, sum/3, sum/3 и в цикле вычитайте 1 из первого индекса и вес i-й гири или не вычитайте или вычитайте из одного из весов, в зависимости от сохраненного знаяения во втором массиве.

Можно вместо второго массива в dp хранить 0, если это состояние невозможно и или номер кучки для последней гири.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы