Блог пользователя train55

I m stuck

Автор train55, история, 4 года назад, По-английски

Can anyone give me the solution or send me the solution to this problem: I have an integer s I want to know the number of ways to express s as a sum of different elements from the array a[].(without repetition). Thank you!!

  • Проголосовать: нравится
  • -20
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

constrains?

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe this is what you need, link

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    He said no repetitions. In that case, try all subsets of a[ ]. Unless the problem limits the values of s and values in the array, I'm not aware of any polynomial-time algorithm.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      So where is a way repeated in the solution(link)?

      Like if as given $$$s$$$=$$$4$$$ and $$$a$$$ = {1,2,3}.

      $$$ways$$$:
      1.{1,1,1,1}
      2.{1,1,2}
      3.{1,3}
      4.{2,2}
      These are the $$$4$$$ possible ways.right?

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        In the first way, you're using 1 4 times. I think that's what the OP meant by repetition.

        → Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This is just basic knapsack dp. Essentially you do the coin change dp solution mentioned above except iterate through the array backwards to avoid repetition.

→ Ответить