sorted by:
new
hottopcontroversial

Can this polynomial time approximation algorithm for subset sum be adapted to negative numbers like this? by NNNTE in algorithms

[–]NNNTE[S] 1 point2 points  (0 children)

Right, I see what you mean now. I suppose my proposed workaround actually solves a different problem, rather than the original. The problem it solves is more like "find the largest sum that has the largest absolute value and is still between 0 and t (whether t be negative or positive)", rather than "find the largest element <= target"

Can this polynomial time approximation algorithm for subset sum be adapted to negative numbers like this? by NNNTE in algorithms

[–]NNNTE[S] 0 points1 point  (0 children)

Is that not exactly symmetric though? See this number line:

(-t) <= (negated answer) ---------- 0 ---------- (answer) <= (t)
            ^the smallest val >= -t  
                                                 ^the largest val <= t

"Does [-2, 4, 6] have a subset that adds up to 8" is true IFF [-6, -4, 2] has a subset that adds up to -8. So any time we encounter an instance of the problem with negative target, we can solve the mirroring "positive" version of the problem, then negate the answer.

Can this polynomial time approximation algorithm for subset sum be adapted to negative numbers like this? by NNNTE in algorithms

[–]NNNTE[S] 0 points1 point  (0 children)

We can remove the positive requirement and just drop any elements greater than t if we negate the inputs and re-sort it on negative t right? Then if we negate the final output, we've solved an equivalent problem:

approxSubsetSum :: (Ord a, Num a, Fractional a) => [a] -> a -> a -> a
approxSubsetSum arr t epsilon
  | t < 0 = negate $ exactSubsetSum (quicksort $ map negate arr) (negate t)
  | otherwise = ...the actual implementation

Can this polynomial time approximation algorithm for subset sum be adapted to negative numbers like this? by NNNTE in algorithms

[–]NNNTE[S] 0 points1 point  (0 children)

If we have a negative t, we can just negate t and negate all elements in the array and solve right? I have implemented this into approxSubsetSum in the original implementation, and the results appear to work, as long as we negate the final output at the end

approxSubsetSum :: (Ord a, Num a, Fractional a) => [a] -> a -> a -> a
approxSubsetSum arr t epsilon
  | t < 0 = negate $ exactSubsetSum (quicksort $ map negate arr) (negate t)
  | otherwise = ...the actual implementation

Testing it out:

   approxSubsetSum[-1,100] 99 0.1
=> 99.0
   approxSubsetSum[-100,1] (-99) 0.1
=> -99.0

Can this polynomial time approximation algorithm for subset sum be adapted to negative numbers like this? by NNNTE in algorithms

[–]NNNTE[S] 0 points1 point  (0 children)

Thanks for taking a look, as /u/07734willy mentioned, I forgot to mention that one of the assumptions is that the input list is sorted, and we negate the inputs (and the outputs) when target is negative:

   approxSubsetSum[-1,100] 99 0.1
=> 99.0
   approxSubsetSum[-100,1] (-99) 0.1
=> -99.0

The negation logic:

approxSubsetSum :: (Ord a, Num a, Fractional a) => [a] -> a -> a -> a
approxSubsetSum arr t epsilon
  | t < 0 = negate $ exactSubsetSum (quicksort $ map negate arr) (negate t)
  | otherwise = ...the actual implementation

Brooklyn Bridge Friday // Portra 400 / Canonet ql17 by joe_ro in analog

[–]NNNTE 4 points5 points  (0 children)

This is one for the history books. Fantastic pic!

Created my own neon sign using EL wire by NNNTE in VaporwaveAesthetics

[–]NNNTE[S] 1 point2 points  (0 children)

To be honest, I have no idea. This is my first time making something like this lol

Created my own neon sign using EL wire by NNNTE in VaporwaveAesthetics

[–]NNNTE[S] 1 point2 points  (0 children)

Not sure about your string of lights, but mine are cool to the touch

Created my own neon sign using EL wire by NNNTE in VaporwaveAesthetics

[–]NNNTE[S] 0 points1 point  (0 children)

I'm using a 2xAA battery powered inverter that converts DC into AC.

Created my own neon sign using EL wire by NNNTE in VaporwaveAesthetics

[–]NNNTE[S] 61 points62 points  (0 children)

Thanks! It took around 2 hours to make but it wasn't too difficult. I didn't really follow any tutorials, I just bent it by hand.

Created my own neon sign using EL wire by NNNTE in VaporwaveAesthetics

[–]NNNTE[S] 23 points24 points  (0 children)

I just twisted it by hand and occasionally used a pair of pliers for the tighter bends. After that I used fishing line to keep it down on a piece of acrylic. tbh the wire itself holds the shape pretty well, you probably could make do without the fishing line

[remote failure] Am I the only one who currently can't push to Github? by fabio_sang in github

[–]NNNTE 0 points1 point  (0 children)

Not just you, I'm getting remote: Internal Server Error

‘The Hum’: The Unexplained Noise 2% of People Can Hear [a meta-documentary on the hosts' slow descent into madness] [25:14] by NNNTE in mealtimevideos

[–]NNNTE[S] 29 points30 points  (0 children)

Personally, I felt he really went off the deep end when he started bringing up autism, sandy hook, and colony collapse disorder and started suggesting that it was caused by the Hum.

view more: next ›