|
Man: Man units
|
#
?
Oct 26, 2018 11:06
|
|
|
|
| # ? Apr 27, 2024 21:50 |
|
|
90s Cringe Rock posted:Man: The worst man page.
|
|
#
?
Oct 26, 2018 11:13
|
|
|
Tree Goat posted:I wrote Way Too Many loving Words about this problem a few years ago: Yo this was a pretty good read, thanks for posting :-)
|
|
#
?
Oct 26, 2018 12:05
|
|
|
Carbon dioxide posted:Not a graph but I still feel it should belong here. It's not even a particularly difficult optimization problem. The solution follows almost immediately from the principle of optimality.
|
|
#
?
Oct 26, 2018 16:27
|
|
|
ultrafilter posted:It's not even a particularly difficult optimization problem. The solution follows almost immediately from the principle of optimality. I am admittedly too lazy to check, but I think you're wrong. The price is not linear so this has more of a feeling of a knapsack problem. Which is hard.
|
|
#
?
Oct 26, 2018 17:16
|
|
|
klafbang posted:I am admittedly too lazy to check, but I think you're wrong. The price is not linear so this has more of a feeling of a knapsack problem. Which is hard. Yeah you want to combine the cheapest combination of sub-orders. Feels knapsacky to me as well
|
|
#
?
Oct 26, 2018 17:53
|
|
|
It seems like pretty straightforward dynamic programming to me -- it has optimal substructure. Let's call C(q) the cost of a single batch of q wings, so C(4) = 4.55. Define OPT(j) as the optimal (minimum) price for ordering j wings. The last decision you make here is "how big is the final batch of wings in your order?" You can then refer to the optimal solution for the rest of the wings. You're constrained by the set of quantities Q = {4, 5, ..., 200}, giving this recurrence: quote:OPT(j) = minq ∈ Q, q < j { OPT(j - q) + C(q) } You'll need base cases of OPT(0) = 0 and C(0) = 0, and it'll probably be necessary to define C(q) = ∞ if q ∉ Q.
|
|
#
?
Oct 26, 2018 18:32
|
|
|
Lysidas posted:It seems like pretty straightforward dynamic programming to me -- it has optimal substructure. Let's call C(q) the cost of a single batch of q wings, so C(4) = 4.55. note that you're trying to order wings so loving lol @ "pretty straightforward"
|
|
#
?
Oct 26, 2018 18:50
|
|
|
Captain Foo posted:note that you're trying to order wings so loving lol @ "pretty straightforward" Hey you only have to write the program once
|
|
#
?
Oct 26, 2018 19:00
|
|
|
I really enjoy how two divergent conversations in this thread (wings, wikipedia math pages being incomprehensible) managed to unify on this page.
|
|
#
?
Oct 26, 2018 19:01
|
|
|
Lysidas posted:It seems like pretty straightforward dynamic programming to me -- it has optimal substructure. Let's call C(q) the cost of a single batch of q wings, so C(4) = 4.55. Good news, I think we're both right. I think your algorithm is good and it does indeed solve the knapsack problem. It's not "simple" though. The formulation is simple, but computationally it is still in NP (the complexity depends on the number of wings, not just on the number of possible orders).
|
|
#
?
Oct 26, 2018 19:50
|
|
|
The wing ordering problem can be solved with dynamic programming. To order n wings, you need to know the cheapest combination of n - k wings and k wings for all k in [0, n/2], so the solution should scale polynomially in n.
|
|
#
?
Oct 26, 2018 20:02
|
|
|
klafbang posted:Good news, I think we're both right. I think your algorithm is good and it does indeed solve the knapsack problem. No, it's quadratic in the number of wings, as ultrafilter described. You need to store O(n) costs, each of which has O(n) possible values. I wrote a Python program that calculates optimal orders. Full output is here. Subset of the output: quote:4 wings: $4.55: [4] e: also by "in NP", I assume you mean "NP-hard" -- this is an optimization problem, but the decision version ("can you order n wings for less than $k?") is in P and therefore isn't NP-hard. Lysidas has a new favorite as of 20:16 on Oct 26, 2018 |
|
#
?
Oct 26, 2018 20:09
|
|
|
How many wings can I order for $420.69
|
|
#
?
Oct 26, 2018 20:28
|
|
|
378, and you'll have 29 cents left over
|
|
#
?
Oct 26, 2018 20:30
|
|
|
Wings aren't actually very good and make a huge mess. Facts.
|
|
#
?
Oct 26, 2018 20:34
|
|
Tater Love 
|
Lysidas posted:378, and you'll have 29 cents left over Now find all possible orders that spend precisely $420.69
|
|
#
?
Oct 26, 2018 20:37
|
|
|
Platystemon posted:Now find all possible orders that spend precisely $420.69 There are none unless you’re going to order 4/5 or 9/10 of a chicken wing.
|
|
#
?
Oct 26, 2018 20:40
|
|
|
zakharov posted:Wings aren't actually very good and make a huge mess. Facts. 
|
|
#
?
Oct 26, 2018 20:41
|
|
|
eating wings is a social experience
|
|
#
?
Oct 26, 2018 20:43
|
|
|
Hurt Whitey Maybe posted:There are none unless you’re going to order 4/5 or 9/10 of a chicken wing. I leave four pence in the “take a penny/leave a penny” dish.
|
|
#
?
Oct 26, 2018 20:50
|
|
|
zakharov posted:Wings aren't actually very good and make a huge mess. Facts. 
|
|
#
?
Oct 26, 2018 21:42
|
|
|
I love the kind of goon who doesnt understand whats going on so they interrupt with the worst possible opinion
|
|
#
?
Oct 26, 2018 21:44
|
|
|
I love that the "vision" boils down to "Have the best everything and be the best at everything, duh!"
|
|
#
?
Oct 26, 2018 22:23
|
|
|
Lysidas posted:No, it's quadratic in the number of wings, as ultrafilter described. You need to store O(n) costs, each of which has O(n) possible values. Wait, why would you buy two sets of nine wings when buying 199, if a single order of 18 is more efficient earlier in the script? Edit: checked, both ways of getting 18 are the same price
|
|
#
?
Oct 27, 2018 01:50
|
|
|
Lysidas posted:e: also by "in NP", I assume you mean "NP-hard" -- this is an optimization problem, but the decision version ("can you order n wings for less than $k?") is in P and therefore isn't NP-hard. We think.
|
|
#
?
Oct 27, 2018 02:24
|
|
|
Hi can we get 25 wings, and also 28 wings, and 28 more wings, and 28 wings on top of that, and 9 wings, and another 28 wings, and 50 wings, and 28 wings again, and uh 25 wings, thanks. Actually you know what I'm trying to keep to a diet right now, just give us 125 wings, 80 wings, 6 wings, and then 28 wings and 9 wings, cheers
|
|
#
?
Oct 27, 2018 03:27
|
|
|
Angepain posted:Hi can we get 25 wings, and also 28 wings, and 28 more wings, and 28 wings on top of that, and 9 wings, and another 28 wings, and 50 wings, and 28 wings again, and uh 25 wings, thanks. Actually you know what I'm trying to keep to a diet right now, just give us 125 wings, 80 wings, 6 wings, and then 28 wings and 9 wings, cheers listen buddy if you want to throw away those 25 cents you can save by using an optimal wing combination instead of a greedy solution, then thats your business, some of us cant afford to throw away that amount of money when buying 497 wings
|
|
#
?
Oct 27, 2018 03:44
|
|
|
Lysidas posted:No, it's quadratic in the number of wings, as ultrafilter described. You need to store O(n) costs, each of which has O(n) possible values. I'm going to be honest here, and say that the thing that is bothering me the most is that the output lists aren't ordered. Also, how bothersome would making a non pandas version of this be? I don't know pandas at all so I can't really follow this code. 
|
|
#
?
Oct 27, 2018 03:50
|
|
|
HardDiskD posted:I'm going to be honest here, and say that the thing that is bothering me the most is that the output lists aren't ordered. This is a memoized recursive implementation, but it's basically the same algorithm: https://repl.it/repls/MemorableOrangeredMatter. My results table is slightly different in terms of the actual orders (but not costs) because it breaks ties in favor of shorter orders.
|
|
#
?
Oct 27, 2018 07:12
|
|
|
Thanks!
|
|
#
?
Oct 27, 2018 22:14
|
|
|
Control Volume posted:I love the kind of goon who doesnt understand whats going on so they interrupt with the worst possible opinion
|
|
#
?
Oct 27, 2018 22:36
|
|
|
Control Volume posted:I love the kind of goon who doesnt understand whats going on so they interrupt with the worst possible opinion 
|
|
#
?
Oct 27, 2018 22:56
|
|
|
|
|
#
?
Oct 28, 2018 04:05
|
|
|
If the percentage of homeless people in Germany and the US is roughly equal, then why are they so much more visible in the latter? Is it because of less social housing, or maybe simply because the weather is better? Also what's up with the high numbers for Australia and New Zealand? (This would actually fit better in the dedicated maps thread over in D&D  )
|
|
#
?
Oct 28, 2018 06:57
|
|
|
System Metternich posted:If the percentage of homeless people in Germany and the US is roughly equal, then why are they so much more visible in the latter? Is it because of less social housing, or maybe simply because the weather is better? Also what's up with the high numbers for Australia and New Zealand? It's not like homeless people are evenly distributed across the country; they're concentrated in cities. So if you live in a city, a larger proportional percentage of the population is homeless than the average for the country as a whole. The US has a large rural population which would probably drive the average way down - if you looked solely at urban populations you'd probably get a pretty different looking map. Unrelated: Kind of weird they didn't colour in Alaska.
|
|
#
?
Oct 28, 2018 07:07
|
|
|
The Cheshire Cat posted:
Alaska homeless are a species of superhumans from what I understand.
|
|
#
?
Oct 28, 2018 07:29
|
|
|
System Metternich posted:If the percentage of homeless people in Germany and the US is roughly equal, then why are they so much more visible in the latter? Is it because of less social housing
|
|
#
?
Oct 28, 2018 07:42
|
|
|
NZ is the same as usual - wider definition of homeless encompassing motel dwellers, people staying in a garage or relatives shed, etc. There's been quite a bit of focus on it in the last year or two.
|
|
#
?
Oct 28, 2018 08:59
|
|
|
|
| # ? Apr 27, 2024 21:50 |
|
|
I presume that the awful part of this is the choice of colors?
|
|
#
?
Oct 28, 2018 10:41
|
|
