### 1e9's blog

By 1e9, 9 years ago,

The problem is similar to asking, you have 2 boxes each having capacity of W(<10000). And you have given a list of item of some capacity c( 100 <= c <= 3000). List can contain at max n (<= 200) items. Now you have to access the list in FIFO order and put those items in any of the two boxes until addition of item overflow each of the boxes. Note: You can not skip any item during processing, if it does not fit stop the process.

I did O(Wn) for each test case. My java solution run in 2 sec approx.

Is there any better solution than this? I thought of greedy but instantly got counter case.

• 0

| Write comment?
 » 9 years ago, # |   0 I got 0.095s with recursive DP. The memo array has two parameters: number of loaded cars and max(sum(car lengths on left side), sum(car lengths on right side)). So it's O(nW), but I guess the recursive solution must explore a small fraction of the possible states on their test cases.
•  » » 9 years ago, # ^ |   0 My recursive was lot slower than iterative one. May be due to the use of library map instead of primitive one. I think your idea of only storing maximum is good. I was saving both left and right sum , that's why same states was executing multiple times. Thanks.
 » 7 years ago, # |   +5 I'm guessing you have to return the max amount of items you can put in the boxes, a basic iterative DP with dimension reduction in memory (pretty standard in dp), basically O(W*N) time but only O(W) memory should to the trick and run basically instantly because the dp array is small enough to be in cache 100% of the time.In order to apply the dimension reduction you just need to make sure that a simple condition is met: all of the information of certain levels is never accesed again, in this case once you have k items in the box you just access k-1, so everything from k-2 to 0 is not used, depending on the problem/implementation you can use 1 or 2 rows instead of N. Note: more complex problems might require m rows.
•  » » 7 years ago, # ^ |   0 I think this makes some sense, but I am not sure I fully understand it. Can you please write down any sort of pseudo code to help me grasp the concept ?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 Sure, I can show you how to optimize knapsack, not this problem because solving it should help you understand how to apply this trick :) //Let's suppose cost and value start from index 1 until N //In this case N is the quantity of items you have, K is the max W of the bag. int solve(int n, int k) { if(k<0) return INF; if(!n) return 0; if(~dp[n][k]) return dp[n][k]; //bitwise not, basically the same as asking if its not -1 return dp[n][k]=min(solve(n-1, k), solve(n-1, k-cost[n])+value[n]); } //Iteratively it would look something like this (same recurrence relationship as recursive) for(int n=1; n<=N; n++) { for(int k=cost[n]; k<=K; k++) { dp[n][k]=min(dp[n-1][k], dp[n-1][k-cost[n]]+value[n]); } } //We can notice that we only need 2 rows, the previous one and the current one //We can also notice that if we are in row n and column k, we can only use the values from row n-1 and from the colums [0,k], which means that if we process colums from right to left can use only 1 row to represent this //Basically with this if we are in column k everything to the right contains the answer for row n, and everything to the left, the answer to row n-1 for(int n=1; n<=N; n++) { for(int k=K; k>=cost[n]; k--) { dp[k]=min(dp[k], dp[k-cost[n]]+value[n]); } } Let me know if you have any doubts.