from typing import List
from typing import Set


def _reconstruct(vals: List[float], weights: List[int], cap: int,
                 dp: List[List[float]]) -> Set[int]:
    """
    Private helper function to reconstruct the included items according to the
    optimal solution using backtracking.
    :param vals: list[float]
    :param weights: list[int]
    :param cap: int
    :param dp: list[list[float]]
    :return: set{int}
    """
    included = set()
    item, curr_cap = len(vals) - 1, cap
    while item >= 1:
        result_without_curr = dp[item - 1][curr_cap]
        if weights[item] <= curr_cap and \
                result_without_curr < \
                dp[item - 1][curr_cap - weights[item]] + vals[item]:
            # Case 2: The current item is included.
            included.add(item)
            curr_cap -= weights[item]
        item -= 1
    if weights[0] <= curr_cap:
        included.add(0)
    return included
    # Running time complexity: O(n)