Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Optimized 0-1 knapsack problem solution in Clear category for Park Benches by swagg010164
from typing import List, Tuple
from collections import defaultdict
# Article to read - https://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem
def park_benches(benches: List[Tuple[int, int]], dist: int) -> int:
# dict to store cumsum for bench with most rightmost coord
memo = dict()
for ind, elem in enumerate(benches):
# print(queue)
if ind == 0:
memo[0] ,memo[elem[1]] = 0, elem[0] + elem[1]
else:
new_memo = {0: 0}
for key in memo:
new_memo[key] = memo[key]
if elem[0] - memo[key] >= dist:
new_memo[elem[1] + key] = min(new_memo.get(elem[1] + key, 1e18), elem[0] + elem[1], memo.get(elem[1] + key, 1e18))
memo = new_memo
return max(memo.keys())
Feb. 22, 2021
Comments:
