1
$\begingroup$

There are two stacks $S_1$ and $S_2$ of books. Each book in stack has a weight. You are given a net weight $W$ of books that can be picked. You have to maximize the number of books that can be picked. Note that each time you can either pick from $S_1$ or $S_2$ only.

eg: $S_1 = \langle 5, 1, 1\rangle$, $S_2 = \langle 1,2,6 \rangle$, $W=10$.

So the answer is $5$ (pick $1$ and $2$ from $S_2$, then all elements from $S_1$)

I know this question can be done with a greedy approach by comparing top elements of both stacks, but can we solve it with the concept of trees?

Is there any other data structure that can be used to solve this problem?

$\endgroup$
  • $\begingroup$ This was an interview problem in which the answer was to use trees,but I can't figure out how?So that's why I asked here if there is any alternative solution as well? $\endgroup$ – Saurabh Oct 6 '17 at 16:28
  • $\begingroup$ Edited the question,the W can be any number,not the maximum value. $\endgroup$ – Saurabh Oct 6 '17 at 16:29
  • $\begingroup$ I don't know what "solve it with the concept of trees" would mean. Why would we want to, given that there already exists an efficient (linear-time) and simple solution for the problem? I suspect there's some additional context or requirements you haven't given us. There's always some other data structure: for instance, I could create a Froobazingus data structure and then never use it. $\endgroup$ – D.W. Oct 8 '17 at 1:18
  • $\begingroup$ No additional context,trees was just one way of solving it,please suggest if you have another solution for the question. $\endgroup$ – Saurabh Oct 9 '17 at 17:47
1
$\begingroup$

The greedy algorithm does not always work. Example: $S_1 = \langle 3, 1, 1,1\rangle$, $S_2 = \langle 2, 2,2\rangle$, $W=6$.

In general, let $S_1 = \langle x_1, \dots, x_k \rangle$ and $S_2 = \langle y_1, \dots, y_h \rangle$. I will assume that individual book weights are positive integers. To solve your problem optimally you can use a sliding-window approach. Compute, for each $i=0,\dots k$, the quantity $X_i = \sum_{j=1}^i x_i$. Similarly, for each $i=0,\dots,h$ compute $Y_i = \sum_{j=1}^i y_i$.

Now start with $i=0$ and $j=h$ and iteratively do the following:

  • If $X_i + Y_j \le W$ consider the solution $(i,j)$ that selects $i$ elements from $S_1$ and $j$ elements from $S_2$ as a candidate solution.
  • If $i=k$ and $j=0$ stop and return the solution that maximizes $i'+j'$ among all candidate solutions $(i',j')$.
  • If $X_i + Y_j \le W$ and $i<k$, or if $j=0$, increment $i$ by $1$.
  • Otherwise, decrement $j$ by $1$.

To see that this algorithm must work consider an optimal solution that selects $i^*$ books from $S_1$ and $j^*$ books from $S_2$. Since, at the end of the algorithm, $i=k$ and $j=0$ there must be some iteration for which $i=i^*$ or $j=j^*$. Consider the first such iteration.

If $i=i^*$ then $j \ge j^*$ meaning that for all $j' = j^*+1, \dots, j$ we must have $X_i + Y_{j'} > W$. This shows that in the next $j-j^*$ iterations $j$ will be decremented until it reaches $j^*$.

If $j= j^*$ then $i \le i^*$ meaning that for all $i' = i, \dots, i^*-1$ we must have $X_{i'} + Y_j > W$. This shows that in the next $i^*-i$ iterations $i$ will be incremented until it reaches $i^*$.

In any case the pair $i=i^*$ and $j=j^*$ is considered by one iteration of the algorithm and, since $X_{i^*} + Y_{j^*} \le W$ the solution $(i^*,j^*)$ must be one of the candidate solutions.

A straightforward implementation requires linear time in the combined size $n$ of the two stacks.

Since you can actually stop computing $X_i$ (resp. $Y_i$) as soon as $X_i \ge M$ (resp. $Y_i \ge M$) you can reduce the time complexity to $O(\min\{n, W\})$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner r =new Scanner(System.in);
        int arr1[]= new int[3];
        int arr2[]= new int[3];
        int w=r.nextInt();
        int temp[]= new int[3];
        int sum=0,cnt=0,flag=1;
        for(int i=0;i<arr1.length;i++){
            arr1[i]=r.nextInt();
        }
        for(int j=0;j<arr2.length;j++){
            arr2[j]=r.nextInt();
        }
        for(int i=0;i<arr1.length;i++){
            for(int j=0;j<arr2.length;j++){
                if(arr1[i]<arr2[j]){
                    temp[i]=arr1[i];
                    if(sum<w){
                        cnt++;
                        sum+=temp[i];
                        flag=0;
                    }
                }
                else{
                    temp[i]=arr2[j];
                    if(sum<w){
                        cnt++;
                        sum+=temp[j];
                        flag=0;
                    }
                }
            }
        }
        if(flag==0){
            if(w==sum){
                System.out.println(cnt);
            }
        }
  }
}
| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This looks a code only reply. I refuse to see it answer Is there any other data structure that can be used to solve this problem? $\endgroup$ – greybeard May 23 at 12:07
  • $\begingroup$ It's hard to tell what's going on from only the code, but this algorithm seems to take time at least $\Omega(|S_1| \cdot |S_2|)$. $\endgroup$ – Steven May 23 at 16:46
  • $\begingroup$ Can you include an explanation of your code, that is, what it does and why it answers the question? $\endgroup$ – 6005 May 24 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.