Technology

Dual Knapsack – Java

By March 5, 2016 No Comments

I came across the following question while I was studying:
You are given a set of integers and you are also allowed to apply sign change operation on all elements. Write an efficient algorithm to find minimum Sum. The minimum Sum should be greater than equal to zero. e.g. if Set is { 2, 1, 3, 4, 2 } Minimum Sum is 0 since you can modify the original set as { -2, -1, -3, 4, 2 }

The input begins with n (the number of integers in the set) followed by n integers. Input ends when n is 0.

For each test case please output the answer in a separate line for each value of n.
Bounds :
0 < n <= 1000

sum of the following n numbers <= 100,000

My solution to the problem is as following:

The time complexity of my solution is O(nlgn), as my algorithm uses the Collectons.sort method which uses a merge sort for sorting the array list.

Naveen

Author Naveen

A Computer Science graduate student, a programmer, photographer, reader and blogger

More posts by Naveen

Leave a Reply