Another way of looking at it, in case none of those landed: - At each state, your decision is (cut this one OR don't cut this one). - Your state has two parts: - Which cookie I'm considering next, - The sum of the *minimum* extra perimeter added by the cookies I chose to cut. - Your value is (the sum of the *maximum* extra perimeter added by the cookies I chose to cut).
You want to maximize the value at each state. When you're done, you'll end up with a bunch of [minimum extra perimeter, maximum extra perimeter] ranges, and you can see which one comes closest to P without going over. On Wed, Apr 18, 2018 at 6:39 PM Xiongqi ZHANG <zhangxion...@gmail.com> wrote: > To make it simple, you can also think it this way. > > The minimum added perimeter for cutting a piece is the weight. (must be > integers) > The maximum added perimeter for cutting a piece is the value. (can be > floats) > > min(sum of all weight, P - existing perimeter) is the maximum weight you > can carry. > > Find out the maximum value you can carry with standard knapsack, say V > The answer is simply min(P, V + existing perimeter) > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/0c6ca684-934d-4db0-97fa-ebb2c1b43c14%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAHaiWHOKLvuR7d6Hp5GwMMNoAeRdXk%2BM-uakchisp%2B%2BfY3Y_ow%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
