using System; | |
/// <summary> | |
/// Solves SPOJ Problem 8545 -- SubsetSum | |
/// URL:http://www.spoj.com/problems/MAIN72/ | |
/// </summary> | |
class Main72 | |
{ | |
static bool isSubsetSumRec(int[] set, int n, int sum) | |
{ | |
if (sum == 0) | |
return true; | |
if (sum != 0 && n == 0) | |
return false; | |
// ignoring this item since if we include, it will | |
// exceede sum. | |
if (set[n - 1] > sum) | |
return isSubsetSumRec(set, n - 1, sum); | |
return isSubsetSumRec(set, n - 1, sum - set[n - 1]) || isSubsetSumRec(set, n - 1, sum); | |
} | |
static void subsetSumRecursiveImpl() | |
{ | |
Console.WriteLine("Computing subset sum using recusion"); | |
int[] set = { 2,3,2}; | |
int sum = 7; | |
bool result1 = isSubsetSumRec(set, set.Length, sum); | |
Console.WriteLine("isSubSetSum: " + result1); | |
} | |
static int computeSubsetSum(int[] set, int n, int sum) { | |
bool[,] dp = new bool[n + 1, sum + 1]; | |
// base case1 : sum = 0 && i is non empty ----> true | |
for (int i = 0; i <= n; i++) { | |
dp[i, 0] = true; | |
} | |
// base case2: sum <> 0 and i=empty set --> false | |
for (int j = 1; j <= sum; j++) { | |
dp[0, j] = false; | |
} | |
// dp[i,j] is true if there is subset from 0 .. i-1 | |
// with sum equal j or j - set[i] | |
for (int i = 1; i < n+1; i++) | |
{ | |
int s_i = set[i - 1]; | |
for (int j = 1; j < sum+1; j++) | |
{ | |
if (j < s_i) | |
dp[i, j] = dp[i - 1, j]; | |
else | |
dp[i, j] = dp[i - 1, j] || dp[i - 1, j - s_i]; | |
} | |
} | |
//// Uncomment following snippet to see the dp Table | |
//for (int i = 0; i < n+1; i++) | |
//{ | |
// for (int j = 0; j < sum+1; j++) | |
// { | |
// Console.Write(dp[i, j]?1:0); | |
// Console.Write(" "); | |
// } | |
// Console.WriteLine(); | |
//} | |
int maxSum = 0; | |
for (int j = 0; j < sum + 1; j++) | |
{ | |
maxSum = maxSum+(dp[n, j] ? j : 0); | |
} | |
return maxSum; | |
} | |
static int solveCase() { | |
int n = Int32.Parse(Console.ReadLine().Trim()); | |
int[] set = new int[n]; | |
int sum = 0; | |
string[] numbers = Console.ReadLine().Trim().Split(); | |
for (int i = 0; i < n; i++) | |
{ | |
set[i] = Int32.Parse(numbers[i]); | |
sum += set[i]; | |
} | |
return computeSubsetSum(set,n,sum); | |
} | |
static void Main(string[] args) | |
{ | |
int noOfCases = System.Int32.Parse(Console.ReadLine()); | |
for (int caseNo = 1; caseNo <= noOfCases; caseNo++) | |
{ | |
Console.WriteLine(solveCase()); | |
} | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment