Skip to content

Instantly share code, notes, and snippets.

@adilakhter adilakhter/Main72.cs
Created Feb 27, 2013

Embed
What would you like to do?
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
You can’t perform that action at this time.