Given a capacity and weights and associated values, find a combination of weights so the value is optimal (minimal/maximal) and the sum of weights >= capacity.
Practical problem: Father and his 10 year old son are going on a skiing trip for 3 days. Costs of tickets are:
| Type of ticket | Cost of ticket per | |||
|---|---|---|---|---|
| Half a day | A day | 2 days | 3 days | |
| Childen's | 12 | 15 | 26 | 39 |
| Adult | 16 | 20 | 34 | 55 |
Decide which combination of tickets is the best (least expensive) for the father and son.
My approach: Create all possible combinations so that their sum is >= 3, store them in a list, get their values, store everything like: [(value1,[weight1,weight2]),(value2,[weight1,weight3]), ...] and use the sorted() function with this as iterable and key=lambda item: item[0]. Then just get the first item from the sorting.
My problem: I don't know how to create all possible combinations.
