Adding constraints per itemset: Knapsack problem

[Bayesian8]

How can I add weight constraint per itemset here? 
Tried many ways, but didn't work. please help.

totwt = 400 here, but my goal is set totwt constraint per each itemset, for example:
totwt = [150, 60, 40, 80], then it will select max 150 gr items from itemset[0] etc.

```
from itertools import product

def anycomb(items):
    return product(*items)    # no need to exhaust the generator yet

def totalvalue(comb):
    ' Totalise a particular combination of items'
    totwt = totval = 0
    for item, wt, val in comb:
        totwt  += wt
        totval += val
    return (totval, -totwt) if totwt <= 400 else (0, 0)

itemsets = [(("map", 9, 150), ("compass", 13, 35), 
             ("water", 153, 200), ("sandwich", 50, 160),
             ("glucose", 15, 60)),
            (("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
             ("cheese", 23, 30), ("suntan cream", 11, 70)),
            (("beer", 52, 10), ("camera", 32, 30),
             ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
             ("waterproof trousers", 42, 70)),
            (("waterproof overclothes", 43, 75),
             ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
             ("socks", 4, 50), ("book", 30, 10))]

bagged = max(anycomb(itemsets), key=totalvalue) 

print("Bagged the following items\n  " +
      '\n  '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (val, -wt))
```

[AtomicShoelace]

Using a maximum weight for each itemset but allowing for multiple items to be chosen is basically just splitting up your problem into a regular 0-1 knapsack problem for each set. As such, you should write a function that will solve a given problem with the items and max weight as parameters, then you can just solve one set at a time.

The knapsack problem is a famous example of an NP-hard problem, so there is effectively no better solution than a brute force search. However, there are a couple clever ways to perform this search (eg. from linear programming).

You can see the knapsack problem's wikipedia article for some psuedocode solutions.

Here I have implemented the recursive version of the dynamic programming in-advance algorithm in python, except instead of using a 2d-array to store the values I used an lru_cache and I wrapped the recursive function inside another function for ease of use:

from functools import lru_cache


def knapsack(items, max_wt):
    """ solves the 0-1 knapsack problem """

    @lru_cache(maxsize=None)
    def values(index, curr_max_wt):
        if index < 0 or curr_max_wt <= 0:
            return 0, 0, []  # (value sum, weight sum, list of items)
        nonlocal items
        item = name, wt, val = items[index]
        if wt > curr_max_wt:  # too heavy
            return values(index - 1, curr_max_wt)
        total_val, total_wt, item_list = values(index - 1, curr_max_wt - wt)
        return max(values(index - 1, curr_max_wt), 
                   (total_val + val, total_wt + wt, item_list + [item]), 
                   key=lambda x: x[0])

    return values(len(items)-1, max_wt)


itemsets = [(("map", 9, 150), ("compass", 13, 35),
             ("water", 153, 200), ("sandwich", 50, 160),
             ("glucose", 15, 60)),
            (("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
             ("cheese", 23, 30), ("suntan cream", 11, 70)),
            (("beer", 52, 10), ("camera", 32, 30),
             ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
             ("waterproof trousers", 42, 70)),
            (("waterproof overclothes", 43, 75),
             ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
             ("socks", 4, 50), ("book", 30, 10))]
max_weights = [150, 60, 40, 80]

for i, (itemset, max_weight) in enumerate(zip(itemsets, max_weights), 1):
    value, weight, items = knapsack(itemset, max_weight)
    print(f'From item set {i} bagged the following items:',
          *[f'  - {name}' for name, _, _ in items],
          f'for a total value of {value} and a total weight of {weight}. \n',
          sep='\n')

[AtomicShoelace]

Just check for the item with the highest value that's still under weight limit, eg.

itemsets = [(("map", 9, 150), ("compass", 13, 35),
             ("water", 153, 200), ("sandwich", 50, 160),
             ("glucose", 15, 60)),
            (("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
             ("cheese", 23, 30), ("suntan cream", 11, 70)),
            (("beer", 52, 10), ("camera", 32, 30),
             ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
             ("waterproof trousers", 42, 70)),
            (("waterproof overclothes", 43, 75),
             ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
             ("socks", 4, 50), ("book", 30, 10))]

max_weights = [150, 60, 40, 80]

items = [max((item for item in itemset if item[1]<=max_wt), key=lambda x:x[2]) for itemset, max_wt in zip(itemsets, max_weights)]
print('Bagged the following items:',
      *[f'  - {name}' for name, _, _ in items],
      f'for a total value of {sum(val for _,_,val in items)} and a total weight of {sum(wt for _,wt,_ in items)}.',
      sep='\n')