##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
AtCoder DP E
This is Knapsack 2 from AtCoder DP Contest: You have items. Each item has weight and value . Your bag holds weight . Find the maximum value you can carry. The constraints are break the standard approach. is impossible when .
You need a different DP formulation. Flip the DP: try dp[value] = minimum weight to achieve exactly that value.