Maximizing book picked using two stacks

Question

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?

Answer 1

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

Answer 2

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);
            }
        }
  }
}