Timus 1005. Stone pile

This is a first post which describes how to solve some particular programming task. Today we will consider Stone pile task from Timus. It is clear and easy. The task sounds like:

Task

Stone pile

Task

You have a number of stones with known weights w1, …, wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones n (1 ≤ n ≤ 20) and weights of the stones w1, …, wn (integers, 1 ≤ wi ≤ 100000) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Limits

Time limit: 1.0 second

Memory limit: 64 MB

Solution

The easiest approach is to check all possible stone pile variants and to test which one has minimal weight difference. I.e. this is brute force approach.

How can we generate all these variants? So, we have 2 piles - first and second. Let’s designate that stone is in the first pile with value 0, and that stone is in the second pile with value 1. Let’s imagine that we have 3 stones, so let’s generate all possible stone placements in 2 piles:

  • 0 0 0 (all 3 stones (w1, w2, w3)are in the first pile)
  • 0 0 1 (w1, w2 are in 1st pile, w3 is in the 2nd pile)
  • 0 1 0 (w1, w3 are in 1st pile, w2 is in the 2nd pile)
  • 0 1 1 (etc…)
  • 1 0 0
  • 1 0 1
  • 1 1 0
  • 1 1 1 (all 3 stones (w1, w2, w3)are in the 2nd pile)

Also we can see that regarding the weight difference first 4 variants are identical to the next 4 variants of stone placements. This means that is it sufficient to check only half of all possible stone placements, i.e. n/2.

Also we can see that stone placements are bit sequences. So all possible placements will be 2n. But since we can check only half of them, then we need to check only 2n-1 placements. In Java/C++ it will be equal to 1 << n-1.

So, summarizing all that, we will have following algorithm:

  • Read input values
  • Generate maximum number of variants we want to check: LIMIT = 1 << n-1
  • Loop from 1 to LIMIT, incrementing by 1 on each loop cycle. Loop variable designates a particular placement variant.
  • In each loop generate weight sum for each stone pile regarding bit order in the loop variable and check if this placement generates minimal weight difference.

Solution code

import java.io.*;
import java.util.*;

public class Timus1005
{
   public static void main(String[] args)
   {
      Scanner scanner = new Scanner(System.in);
      
      int n = scanner.nextInt();
      int[] stones = new int[n];
      
      for (int i=0; i<n; i++) {
          stones[i] = scanner.nextInt();
      }
      
      int diff = bruteForce(stones);
      
      PrintWriter out = new PrintWriter(System.out);
      out.println(diff);
      out.flush();
   }
   
   static int bruteForce(int[] stones) {
       final int N = stones.length;
       final int LIMIT = 1 << N-1;
       int diff = Integer.MAX_VALUE;
       
       for (int i=0; i<=LIMIT; i++) {
           int sum1=0, sum2=0;
           int k=i;
           for (int j=0; j<N; j++) {
               if ((k & 0x1) == 0) sum1+=stones[j];
               else sum2+=stones[j];
               k = k>>1;
           }
           int diffi = (sum1>=sum2) ? sum1-sum2 : sum2-sum1;
           if (diffi<diff) diff = diffi;
       }
       return diff;
   }
}
More Reading
Older// First post