Subset sum algorithm but with greater or equal sum

Revision en1, by Night_Lord, 2021-01-03 07:48:35

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.

Tags # 2d dp, subset sum

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Night_Lord 2021-01-03 07:49:46 10
en1 English Night_Lord 2021-01-03 07:48:35 896 Initial revision (published)