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

Doubt:Subset sum DP solution using 1D array.
Автор charany1, 10 лет назад, По-английски

Hi there, I came across this dp solution for subset sum problem which uses O(sum) space rather than O(n*sum). The array is filled in a reverse manner i.e. starting from sum.

But I am not able to understand it properly,I know what is happening but not able to make clear sense out of it. Can someone please explain, how its working.

bool is_subset_sum(vector<int>& v,int sum)
{
int n=v.size();
vector<int>dp(sum+1,0);
dp[0]=1; //sum =0 is always attainable.

for(int i=0;i<n;i++)for(int j=sum;j>=v[i];j--)
     dp[j]|=dp[j-v[i]];

return dp[sum];

}
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

First of all, please describe the exact formulation of the version of the subset sum problem that the algorithm intends to solve. If it's something like <<To mark all possible sums with "1"-s and all impossible with "0"-s>>, dp[j]=dp[j-v[i]] should be dp[j]=max(dp[j],dp[j-v[i]])

If you wonder why does the algorithm require reverse order — such order allows to use each value v[i] at most once; using direct order, the same in all other fragments algorithm allows to use arbitrary quantities of each value v[i].

UPD: My mistake at the end of the first paragraph, sorry. dp[j]|=dp[j-v[i]] (with |= operator) looks ok. Thanks to tenshi_kanade's reply below.

→ Ответить