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$
4
  • $\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, 2017 at 16:28
  • $\begingroup$ Edited the question,the W can be any number,not the maximum value. $\endgroup$
    – Saurabh
    Oct 6, 2017 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, 2017 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, 2017 at 17:47

2 Answers 2

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\})$.

$\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);
            }
        }
  }
}
$\endgroup$
3
  • 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, 2020 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, 2020 at 16:46
  • $\begingroup$ Can you include an explanation of your code, that is, what it does and why it answers the question? $\endgroup$ May 24, 2020 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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