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...
Какое оптимальное решение для трехмерного рюкзака?
