Блог пользователя Night_Lord

Автор Night_Lord, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Greedy

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Why this looks similar to codechef long challenge question?