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

Какое оптимальное решение для трехмерной задаче о рюкзаке?

https://codeforces.com/problemset/gymProblem/105244/C
Космический исследователь планирует отправиться в экспедицию к удалённой планете. На его пути в заданном порядке есть несколько космических объектов, каждый из которых обладает своей уникальной ценностью для исследования. При этом каждый объект требует определенного количества энергии (в единицах) и времени (в днях) для его изучения.

Однако у исследователя есть ограничение на количество доступной энергии K
и времени M, чтобы завершить миссию. Необходимо составить оптимальную последовательность посещения объектов, которая максимизирует научную ценность экспедиции, учитывая ограничения на энергию и время.
Входные данные
В первой строке через пробел заданы число 1≤N≤100
— количество космических объектов, а также ограничения по энергии 1≤K≤100 и времени 1≤M≤100
В последующих N
строках для каждого объекта через пробел заданы его научная ценность 0≤V≤150, количество энергии 1≤F≤50 и время в днях 1≤T≤20необходимые для исследования.
Выходные данные
В первой строке выведите число — максимальную научную ценность исследования. Во второй строке — последовательность посещения объектов.
Предполагается, что объекты нумеруются последовательно, начиная с единицы. Исследователь может их посещать только в заданном порядке.
Если не получится исследовать ни один объект, выведите 0.
Если возможных решений несколько, выведите любое из них.
https://codeforces.com/problemset/gymProblem/105244/C
Мое решение:
_dp=[]
def _recovery_indexes(_dp:list, *, a, k, f, i:int=-1, ans=None):
    if ans is None:
        ans = set()
    if i==-1:
       i=len(_dp)-1
    # ------------------------------
    if _dp[i][k][f]==0:
        return
    if _dp[i-1][k][f]<_dp[i][k][f]:
        ans.add(i)
        _recovery_indexes(_dp, a=a, f=f - a[i - 1]['f'], k=k - a[i - 1]['k'], i=i - 1, ans=ans)
    else:
        _recovery_indexes(_dp, a=a, f=f, k=k, i=i - 1, ans=ans)
    return ans


def cosmos(a:list, F:int, K:int):
    global _dp
    for i, x in enumerate(a):
        for f in range(F, x['f']-1, -1):
            for k in range(K, x['k']-1, -1):
                if _dp[i][k][f]<_dp[i][k-x['k']][f-x['f']]+x['v']:
                   _dp[i+1][k][f]=_dp[i][k-x['k']][f-x['f']]+x['v']
                else:
                    _dp[i+1][k][f]=_dp[i][k][f]
    _cache=_recovery_indexes(_dp, a=a, f=F, k=K)
    return _dp[-1][K][F], _cache


if __name__ == '__main__':
    (n, F, K) = tuple([int(x) for x in input().rstrip().split()])
    a=[]
    for t_itr in range(n):
        (vi, fi, ki ) = tuple([int(x) for x in input().rstrip().split()])
        a.append({'f': fi, 'k': ki,'v': vi})
    _dp = [[[ 0 for _ in range(F+1)] for _ in range(K+1)] for _ in range(n+1)]
    result = cosmos(a, F, K)
    print(result[0])
    if result[0]>0:
       print(sorted(result[1]))

Не могу понять что не так.
Первые тесты проходят.
Не проходит тест:

4 40 30
30 7 10
50 16 12
80 12 20
15 5 7

Ожидается:

110
1 3

Получено:

95
1 2 4

По сути алгоритм модифицированный алгоритм духмерного рюкзака:
https://cp-algorithms.com/dynamic_programming/knap...
Какое оптимальное решение для трехмерного рюкзака?
  • Вопрос задан
  • 34 просмотра
Подписаться 1 Средний 2 комментария
Пригласить эксперта
Ваш ответ на вопрос

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

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