CODEWITHSUNDEEP
javaalgorithm
Mayur Kulkarni
Mayur Kulkarni

Reputation: 1316

Adding up least elements in sequence

I have a certain number of triplets and I want to add up numbers in such a way that the sum remains minimum and you can select only one number in a certain triplet. eg:

10 10 1   //minimum 1
1  10 21  //minimum 1
10 1  10  //minimum 1 Ans : 1+1+1 = 3

However you cannot select adjacent element in same column.

10 10 1 //select 1
10 10 1 //cannot select 1, that's adjacent!
10 10 1 //safe to select 1

But the problem is, in case of a tie, I need to scan the next triplet in the sequence and make sure not the select the number in previous sequence for obtaining maximum profit eg:

10 10 10  // step 2.select 10 from column 1 or 2
10 10 1   // step 1.make sure not to select element in column 3 in previous sequence
          // step 3. select 1 from column 3

Since we cannot replace the position of Scanner so I cannot move the scanner's readLine to the previous position, how can I scan ahead of time?

My take : (Since the range of number is large I'm using BigInt)

for(long j=0; j<noOfTriples ; j++){
    firstNumber = in.nextBigInteger();
    secNumber = in.nextBigInteger();
    thirdNumber = in.nextBigInteger();

    if(areEqual(firstNumber, secNumber, thirdNumber)){
        while(true){
             firstNumber2 = in.nextBigInteger();
             secNumber2 = in.nextBigInteger();
             thirdNumber2 = in.nextBigInteger();
             noOfTriples--;
                if(areEqual(firstNumber2, secNumber2, thirdNumber2)){
                    count.add(secNumber2); // add any number to the count
                                          // since all of them are same
                }else
                    break;
                }   

    pass(firstNumber, secNumber, thirdNumber, least(firstNumber2, secNumber2, thirdNumber2));
    //pass adds up the minimum of three to the count 
    //where the last field indicates which element to NOT use while adding &
    //least returns minimum of the three
    }else
    pass(firstNumber, secNumber, thirdNumber, -1);  //-1 indicates no bias
}

Edit :

  1. sprinter pointed out, I need to scan the entire list of triplets. Scanning only 1 ahead in sequence won't help.
  2. The number of inputs may be upto a million, hence exhaustive search won't help.

Upvotes: 4

Views: 86

Answers (2)

Pournima Bedarkar
Pournima Bedarkar

Reputation: 392

I believe this is a problem of Dynamic Programming.

Lets keep a state F(idx, prev) where idx denotes the current sequence at which you are and prev denotes the item number you have added from the just previous sequence. So, we can migrate to the new state F(idx+1, new_prev) such that new_prev is not equal to prev according your problem statement. Pseudo Code:

F(idx, prev) {

     if ( idx == n+1 ) return 0; //Done with shopping on all N triplets

     ans = INFINITY

     for all item_nums from 1 to 3
            if ( item_nums != prev ) ans = min(ans, cost of item_num in shop_num idx + F(idx+1, item_nums)

    return ans
}

Upvotes: 2

sprinter
sprinter

Reputation: 27976

You seem to be assuming that you only need to look one set ahead to decide which of the current set to select to end up with a minimum. That's not correct. If you have (9, 3, 5), (8, 4, 7), (6, 1, 8) then looking at the first two you would pick 5 and 4. But once you consider the third set then you see that you should have picked 7 and 3 so that you have the option of picking 1. In fact, because the final set can have arbitrarily large number you don't actually know the right options to select until you've seen all sets.

The conclusion from all of that is that you need to use a more complex algorithm to minimise the sum. Given you have many items an exhaustive search is not an option. However let's start with that so you can see what it would look like:

Let's assume you have read in all your inputs and stored them in a List<List<Integer>> structure.

int minSum(int index, int previous, List<List<Integer>> inputs) {
    if (index >= inputs.size())
        return 0;
    else
        return IntStream.range(0, 3)
            .filter(n -> n != previousIndex)
            .map(n -> minSum(index + 1, n, inputs)).min();
}

Hopefully you're comfortable with Java 8 and can understand this code.

It gets more complicated now as you need to prune the search space for performance reasons. In other words you have to avoid searching options that you can deduce will never result in a lower total.

For example, you have the sets (1, 8, 5), (2, 3, 6), (4, 9, 2). Your algorithm looks at the option 1+3+4 and gets a total of 7. The next value it looks at is the 8 in the first set. But it's obvious that there's no need to even consider that option because it's already larger than the smallest total to date (i.e. 7) so any option including it cannot possibly result in a smaller total.

Hopefully that'll give you enough of a hint. Perhaps submit a separate question on these types of pruning algorithms if you get stuck.

Upvotes: 1

Related Questions