提问者:小点点

在子集和问题中,当我取memo[sum][size]时,我必须加sum<0,但在mem[size][sum]的情况下,我不知道为什么。请解释一下


'''
#include<bits/stdc++.h>
using namespace std;

int issubseset(vector<int> subset,int size,int sum,vector<vector<int>>&memo){
   // if(sum<0)return 0;
    if(sum==0)  return 1;
    if(size<0) return 0;
    
    if(subset[size]>sum) issubseset(subset,size-1,sum,memo);
    if(memo[size][sum]>=0) return memo[size][sum];
    memo[size][sum] = issubseset(subset,size-1,sum-subset[size],memo)||issubseset(subset,size-1,sum,memo);
    return memo[size][sum];
}

int main(){
    vector<int> subset{3, 34, 4, 12, 5, 2};
    int sum=9;
    std::cout << subset.size() << std::endl;
    vector<vector<int>> memo(subset.size(),vector<int>(sum+1,INT_MIN));
    printf("%s",issubseset(subset,subset.size()-1,sum,memo)?"true":"false");
}
'''

问题::

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
  1. 当我将memo从memo[size][sum]交换到memo[sum][size]时,我必须取消对issubset函数的第一行的注释。
  2. 如果我只是更改memo的形状,它不应该有任何影响,因为数组将按照递归填充,并且我已经覆盖了基本情况。如果memo[size][sum]可以在没有“if(sum<0)”行的情况下工作,为什么memo[sum][size]不能工作。

共1个答案

匿名用户

您对您的问题的描述很难理解,为什么不发布问题本身,然后发布您的代码;-)

我想在很难把情况弄清楚的时候帮你。