rlajkalspowq's blog

A knapsack optimizing problem
By rlajkalspowq, history, 5 years ago, In English

You're given $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, you need to count the number of ways to choose some of them (no duplicate) to make the sum equal to $$$S$$$. Print the answer in modulo $$$10^9+7$$$. How to solve this problem in polynomial time?

Note: The $$$n,S$$$ can be as large as $$$10^5$$$ so using single DP can't work. Using polygon $$$ln$$$ or $$$exp$$$ might work. But I don't know how to use them (I've just heard of it). Can anyone explain it?

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rlajkalspowq (previous revision, new revision, compare).

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

I think this should work . let's make a dp array where dp[i] = no. of ways to make sum i .
Now we don't want to repeat our items so we are going to iterate from the end of sum .
For more info watch Errichto DP tutorial 2 . (Well actually I don't remember the exact number but I think it's 2 ) .

Code
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    This is actually $$$\mathcal O(n^2)$$$. What if $$$n=10^5$$$

    I think it can be solved using polygon $$$ln$$$ and $$$exp$$$. (I've just heard of it and don't know how to use). Can anyone explain it?

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

Auto comment: topic has been updated by rlajkalspowq (previous revision, new revision, compare).

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

By Wikipedia, it is NP problem

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

You can use a observation that if S <=10^5, then there can be atmax O(sqrt(S)) different value of elements in the array. You can batch process each value together to get a O(S*sqrt(S)) complexity.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

There is an $$$O(N + S log(S))$$$ algorithm for subset sum using "polygon" $$$ln$$$ and $$$exp$$$ explained in this paper ( https://arxiv.org/pdf/1807.11597.pdf ) and in the editorial for this CodeChef Long Challenge problem ( https://www.codechef.com/JUNE20A/problems/PPARTS ). The CodeChef problem is, as expected, a much more complicated version of the subset sum problem, but the same ideas that solve that problem can be used to solve your problem (yours is a special case where $$$b_i = 1$$$).

For non-NTT friendly modulos like your $$$10^9 + 7$$$, you can compute convolutions modulo three different NTT-friendly primes and combine with CRT, or use Karatsuba instead of NTT (see problem https://judge.yosupo.jp/problem/convolution_mod_1000000007 ).

For the subset sum problem, you can also take a look at the solutions for ( https://judge.yosupo.jp/problem/sharp_p_subset_sum ). The problem here uses NTT-friendly modulo, though.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi there is one question find minimum number of a_i that sum = S, or -1 if not possible how to solve that
    Also we can take any number of copies of a_i,
    But constraints are very high like a_i ,n,S<=10^6

    Someone asked me this question on telegram. But I am stuck on it from many days and I could not think of any approach,
    I also referred this interesting codeforces blog but still stuck link

    I also tried each a_i in powers of 2 but dp seems too costly, is there any greedy solution to this question.

    P.S- please forgive me for posting this here

    → Reply