taklo's blog

Help Regarding Dp Problem from atcoder educational dp contest
By taklo, history, 5 years ago, In English

https://atcoder.jp/contests/dp/tasks/dp_e

this is knapsack problem with tough constraints so making dp table is not feasible (100*(10^9))

How this can be approcahed ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sorta like coin exchange problem, where you try to get the minimum weight for each possible value

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

https://www.youtube.com/watch?v=FAQxdm0bTaw

→ Reply