1e9's blog

UVA 10261, ferry loading, best Solution?
By 1e9, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      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.

      → Reply