In a subset sum problem always we have to find a subset which equals a given sum. Like in this example if $$$A=[1,2,3,4,5,15,21]$$$ and $$$sum=8$$$. Then the optimal subset would be [3,5]. But what if we consider all greater or equal subsets ? Like $$$[15]$$$,$$$[21]$$$ these are the minimum element subsets with sum greater or equals the given sum. How can I implement it?
Although general subset sum algorithm I learnt is-
bool T[n+1][sum+1];
for(int j=1;j<=sum;++j)
{
T[0][j]=false;
}
for(int i=0;i<=n;++i)
{
T[i][0]=true;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=sum;++j)
{
if(arr[i-1]>j)
T[i][j]=T[i-1][j];
else
T[i][j]=T[i-1][j]||T[i-1][j-arr[i-1]];
}
}
Can I able to change some snipets of code and get my output value or I have to learn something else. Thanks in advance.
Greedy
Why this looks similar to codechef long challenge question?