Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
knapsack 0/* DP solution in Clear category for Family Dinner by juestr
from functools import lru_cache
from itertools import accumulate
from typing import List
def best_plates(stacks: List[List[int]], guests: int) -> int:
# This is very much like the standard knapsack 0/1 dynamic programming solution.
# Instead of max() over a binary choice per new item there are up to stack-length
# choices for each new stack, and weight corresponds to plates taken from stack.
summed_beauty = [list(accumulate([0] + stack)) for stack in stacks]
@lru_cache(maxsize=None)
def beauty(nstacks: int, nguests: int) -> int:
return nstacks and nguests and \
max(beauty(nstacks-1, nguests-i) + summed_beauty[nstacks-1][i]
for i in range(min(len(stacks[nstacks-1])+1, nguests+1)))
return beauty(len(stacks), guests)
May 14, 2020
