Knapsack problem - variant - O(C) solution

#1

Another variant that’s driving me crazy (I’d love to see the answers to the variants in a future edition!) is the O© solution for the Knapsack problem. I’ve tried using hashtables where I hash the weight remaining, and I’ve tried where I hash the current weight of the knapsack, but neither work.

0 Likes
#2

Here is my DP based solution to this problem. It uses an array to map from the index of the capacity to its corresponding target capacity, and a dictionary to map the inverse relation.

To know which capacities are to be included in C, an auxiliary set is built and afterwards transformed into a sorted list to build the aforementioned mapping array,

Algorithm 
def optimum_subject_to_capacity(items, capacity):
    
    cap_mapping_set = {0}
    for item in items:
        for mapped_weight in list(cap_mapping_set):
            if (item.weight + mapped_weight <= capacity):
                cap_mapping_set.add(item.weight + mapped_weight)
    cap_mapping = sorted(list(cap_mapping_set))
    cap_mapping_dict = dict((weight, idx) for idx, weight in enumerate(cap_mapping))
    
    current = [0] * len(cap_mapping)
    prev = None

    for j in range(1, len(items) + 1):
        prev = current.copy()
        for i in range(1, len(cap_mapping)):
            item = items[j - 1]
            prev_value = prev[i]
            cap = cap_mapping[i]
            with_item_value = prev[cap_mapping_dict[cap - item.weight]] + item.value if ((cap - item.weight) in cap_mapping_dict) else current[i-1]
            current[i] = max(prev_value, with_item_value)

    return current[-1]
0 Likes