6 ms·

This is a classic dynamic programming problem. You create an array of bools of length 4394+1, initialize to False, and fill it left to right with True on the sp

This is a classic dynamic programming problem. You create an array of bools of length 4394+1, initialize to False, and fill it left to right with True on the specific amount of cents that can be covered (this is possible because nothing has a negative price). Then if the final element is True the solution exists, and all solutions can be generated by back-tracking. It's polynomial if the input is represented in unary form (like in the regex version down below), and exponential if the input is represented in binary. BTW, if you want you can even express this as a certain regex+input combo: Regex: (a^122|a^275|a^185|...)+ Input: a^4394 Where a^N means "a" repeated N times, and of course the regex must cover the entire string. And, if your regex engine can find all matches, then it would also find all solutions.

hackcasual 5y ago
If the values are small enough. The problem is that the length of the unary form grows exponentially
- nroets 5y ago
  Here's that runs in O(√2^n) time and space. And with careful implementation it will never be significantly slower than the above DP algorithm. 1. Spilt the toys in two sets (A and B) of similar size. 2. Generate a sorted list L of all the possible sums that can be made with the toys in set A. If two sums are equal, keep only one. 3. Generate a sorted list M of all the possible sums that can be made with the toys in set B. If two sums are equal, keep only one. 4. Iterate through L forwards and through M backwards looking for two sums that together make up the target amount.
  - H8crilA 5y ago
    The lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the target sum and M is the number of toys this algorithm runs in O(2^N * M * log(M))
    - nroets 5y ago
      No. Small n in only 21. You split the toys in a set of 10 and a set of 11. What I'm really describing is the Meet In The Middle algorithm: https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-m...
dinobones 5y ago
Interesting.. It's somehow tough for me to accept that a "NP complete" problem can be solved with a regular language. You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)... But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?) It feels like an abuse of regular languages and automata, and I'm not sure it works... This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?
- yuubi 5y ago
  This is a pseudopolynomial time algorithm: polynomial in the magnitude of an important number, not in the number of bits that it takes to write it down. Problems with those kind of algorithm available don't make P=NP because the problems that don't have known pseudopolynomial solutions, when reduced to problems that do, end up with numbers with logs (rather than magnitudes) polynomial in the size of the original problem. In real life, numbers are often of human scale (rather than the kind you get from reducing a hard SAT instance to knapsack) and a pseudopolynomial algorithm is great.
- deleted 5y ago
  [deleted]
- H8crilA 5y ago
  Every state that means "a full toy has just been scanned" is a valid accepting state. In fact you don't need separate states for each toy, you only need self-loop of appropriate length. (Also, this is an NFA, not a DFA) The language of valid parentheses up to size 2^5 is obviously regular, it's even finite.
akersten 5y ago
I'm not understanding the "fill it from left to right with true on the specific amount of cents [and if it fits perfectly, you found a solution]." Isn't finding that "specific amount of cents [e.g. which choice of items achieves that amount]" the crux of the problem here that is glossed over? How would you test each combination to fit this boolean array without trying all of them brute force?
- jtsiskin 5y ago
  Start by only considering the Yo Yo, that is easy to fill out. Now consider both the Yo Yo and Doll, that is also easy to fill out given the current array. Then continue.
  - H8crilA 5y ago
    Hmm, true, addition is commutative, so you can reorder the elements however you want. Though it doesn't change the O() complexity you may get some performance tuning by starting with the largest elements. If we're at fine-tuning, one thing you can do is divide all numbers by the GCD of all numbers, assuming that the GCD is not just 1.
- H8crilA 5y ago
  $0.00 is always achievable (choose nothing), and negative values are never achievable. Is $0.01 achievable? Well, take all items, subtract their price from $0.01 and see if any of the results are achievable. If so, $0.01 is achievable. Repeat for $0.02, $0.03, ... This works because by the time you're processing $X you already know the answers to all values smaller than $X (and no item has a negative price).
AlexanderTheGr8 5y ago
I understand your solution, but is it really "Dynamic Programming"? DP requires that the problem can be broken down into subproblems. Also your method requires just quadratic time, right? (It's still pseudo-polynomial though.) I think it should take quadratic time because for every item you find, you loop through the entire array, and whenever you see a 'True', you add the current item's price in it and make that new entry 'True'. You do this for all 'N' items and then in the end, check whether the last index in the array is 'True'. Did I miss something?
- lrem 5y ago
  https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... calls it dynamic programming.
- deleted 5y ago
  [deleted]
- xxs 5y ago
  The integer version of knapsack one is considered dynamic programming (use cents to represent the dollar value). It's pseudo polynomial - it's effectively O(TotalWeight * Items) if the items can be added once only.
- deleted 5y ago
  [deleted]
- Cu3PO42 5y ago
  I also know this approach as Dynamic Programming. While the subproblem is not cleanly seperated it is present in the sense that you consider one element first and then deal with the rest later, never touching the first again. And yes, the runtime here is polynomial, however it is polynomial in the price k, which only needs log k bits to encode in the input. Therefore it is exponential in the encoding length. These algorithms are called pseudo-polynomial.
- H8crilA 5y ago
  The subproblem is covering $0.00 (always possible), then covering $0.01, then covering $0.02, then covering $0.03, ... Yeah the time complexity is O(N*M), where N is the value of the target added up price (size of the unary representation), and M is the number of items.

hackcasual 5y ago

If the values are small enough. The problem is that the length of the unary form grows exponentially

nroets 5y ago
Here's that runs in O(√2^n) time and space. And with careful implementation it will never be significantly slower than the above DP algorithm. 1. Spilt the toys in two sets (A and B) of similar size. 2. Generate a sorted list L of all the possible sums that can be made with the toys in set A. If two sums are equal, keep only one. 3. Generate a sorted list M of all the possible sums that can be made with the toys in set B. If two sums are equal, keep only one. 4. Iterate through L forwards and through M backwards looking for two sums that together make up the target amount.
- H8crilA 5y ago
  The lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the target sum and M is the number of toys this algorithm runs in O(2^N * M * log(M))
  - nroets 5y ago
    No. Small n in only 21. You split the toys in a set of 10 and a set of 11. What I'm really describing is the Meet In The Middle algorithm: https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-m...

dinobones 5y ago

Interesting.. It's somehow tough for me to accept that a "NP complete" problem can be solved with a regular language. You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)... But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?) It feels like an abuse of regular languages and automata, and I'm not sure it works... This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?

yuubi 5y ago
This is a pseudopolynomial time algorithm: polynomial in the magnitude of an important number, not in the number of bits that it takes to write it down. Problems with those kind of algorithm available don't make P=NP because the problems that don't have known pseudopolynomial solutions, when reduced to problems that do, end up with numbers with logs (rather than magnitudes) polynomial in the size of the original problem. In real life, numbers are often of human scale (rather than the kind you get from reducing a hard SAT instance to knapsack) and a pseudopolynomial algorithm is great.
deleted 5y ago
[deleted]
H8crilA 5y ago
Every state that means "a full toy has just been scanned" is a valid accepting state. In fact you don't need separate states for each toy, you only need self-loop of appropriate length. (Also, this is an NFA, not a DFA) The language of valid parentheses up to size 2^5 is obviously regular, it's even finite.

akersten 5y ago

I'm not understanding the "fill it from left to right with true on the specific amount of cents [and if it fits perfectly, you found a solution]." Isn't finding that "specific amount of cents [e.g. which choice of items achieves that amount]" the crux of the problem here that is glossed over? How would you test each combination to fit this boolean array without trying all of them brute force?

jtsiskin 5y ago
Start by only considering the Yo Yo, that is easy to fill out. Now consider both the Yo Yo and Doll, that is also easy to fill out given the current array. Then continue.
- H8crilA 5y ago
  Hmm, true, addition is commutative, so you can reorder the elements however you want. Though it doesn't change the O() complexity you may get some performance tuning by starting with the largest elements. If we're at fine-tuning, one thing you can do is divide all numbers by the GCD of all numbers, assuming that the GCD is not just 1.
H8crilA 5y ago
$0.00 is always achievable (choose nothing), and negative values are never achievable. Is $0.01 achievable? Well, take all items, subtract their price from $0.01 and see if any of the results are achievable. If so, $0.01 is achievable. Repeat for $0.02, $0.03, ... This works because by the time you're processing $X you already know the answers to all values smaller than $X (and no item has a negative price).

AlexanderTheGr8 5y ago

I understand your solution, but is it really "Dynamic Programming"? DP requires that the problem can be broken down into subproblems. Also your method requires just quadratic time, right? (It's still pseudo-polynomial though.) I think it should take quadratic time because for every item you find, you loop through the entire array, and whenever you see a 'True', you add the current item's price in it and make that new entry 'True'. You do this for all 'N' items and then in the end, check whether the last index in the array is 'True'. Did I miss something?

lrem 5y ago
https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... calls it dynamic programming.
deleted 5y ago
[deleted]
xxs 5y ago
The integer version of knapsack one is considered dynamic programming (use cents to represent the dollar value). It's pseudo polynomial - it's effectively O(TotalWeight * Items) if the items can be added once only.
deleted 5y ago
[deleted]
Cu3PO42 5y ago
I also know this approach as Dynamic Programming. While the subproblem is not cleanly seperated it is present in the sense that you consider one element first and then deal with the rest later, never touching the first again. And yes, the runtime here is polynomial, however it is polynomial in the price k, which only needs log k bits to encode in the input. Therefore it is exponential in the encoding length. These algorithms are called pseudo-polynomial.
H8crilA 5y ago
The subproblem is covering $0.00 (always possible), then covering $0.01, then covering $0.02, then covering $0.03, ... Yeah the time complexity is O(N*M), where N is the value of the target added up price (size of the unary representation), and M is the number of items.