Night_Lord's blog

By Night_Lord, history, 3 years ago, In English

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.

  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Greedy

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why this looks similar to codechef long challenge question?