0/1 Knapsack and colored items with conditions

Правка en1, от Mr.Awesome, 2020-11-14 19:29:58

Hello cf,

I'm trying to solve this 0/1 Knapsack problem:

We have N items with each item characterized by weight, price and color (white, blue, red or black).

We have to choose 12 items with maximum total price such as the sum of their weight is <= W and the choosed items fullfill these conditions:

only 1 white item between 3 and 5 blue items between 3 and 5 red items between 1 and 3 black items I tried this backtracking solution (take or leave current item and continue) wich work fine:

Backtrck solution

This work fines but with an exponential complexity so I tried to add memoization (caching: dp[i][currWeight][numW][numBlue][numR][numBlack]) but it doesn't work anymore.

Can any body explain why the memoization doesn't work here, or share his personal approach to solve this problem ?

Costraints:

N <= 100 W <= 1000

PS I've seen this problem somewhere before but I don't have a link, can anybody provide a link of a similiar problems ?

Теги dp, 0/1 knapsack, #optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Mr.Awesome 2020-11-14 20:42:30 719
en2 Английский Mr.Awesome 2020-11-14 19:31:43 11
en1 Английский Mr.Awesome 2020-11-14 19:29:58 2048 Initial revision (published)