I have task about knackpack problem. But for each subject in knackpack, we have two sets of weight-value parameters. For example:
- Beer 1kg 15$, 2kg 20$
- Water 5kg 30$, 10kg 40$
...etc
And we can choose only 1 set of weight-value parameter for each item.
So, what solution I see:
- Generated all unique combinations of pair weigth-value from 2 array. In out we have 2n combinations.
- For all combination we apply knackpack algorithm, then choose solution with max value - it's a best solution.
About problem - if we have about 10-15 items, it's normal. But we need solve this task for 1000 item, so it's 21000 unique combination.
Generate unique combine:
E=[[],[]]
weight1 = [1 2 3 4 5]
weight2 = [6 7 8 9 10]
for choices in itertools.product([0, 1], repeat=len(off)):
E[0].append([(on[j] if choice else off[j]) for j, choice in enumerate(choices)])
value1 = [10 20 30 40 50]
value2 = [60 70 80 90 100]
for choices in itertools.product([0, 1], repeat=len(off)):
E[1].append([(on[j] if choice else off[j]) for j, choice in enumerate(choices)])
If I do it for 30 item - my VDS go to down.
Please, suggest your solution to this problem.