shank_punk's blog

Spoj problem WEIGHT1

By shank_punk, 10 years ago, In English

How do I solve This problem efficiently ?

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

It's classical DP problem.

a[0] = true;
for (int i = 0; i < n; ++i)
   for (int j = W; j >= 0; --j)
      if (a[j]) a[j + w[i]] = true;
→ Reply