题目描述

有n种不同大小的数字Ai，每种各Mi个。判断是否能从这些数字中选出若干个使它们的和恰好为K。

这个问题可以用DP求解，递推关系式的定义会影响最终的复杂度。

第一种定义：

dp[i+1][j]，用前i种数字是否能加和成j

为了用前i种数字加和成j，也就需要能用前i-1种数字加和成j,j-Ai,···,j-MiAi中的某一种。由此我们可以定义如下递推关系：

dp[i+1][j]=(0<=k<=Mi且K*Ai<=j时存在使dp[i][j-k*Ai]为真的K)

#include
    
     #include
     
      using namespace std;int n,K;int a[100],m[100];///a表示数字大小，m表示这个数字的个数bool dp[100][100];///dp数组void solve(){    dp[0][0]=true;    for(int i=0; i
     
    

但是这种方法的时间复杂度比较大，因为一般用DP求取bool结果的话会有不少浪费，在这个问题中，我们不仅要求出能否构成目标的和数，同时把得到时Ai这个数还剩下多少个可以使用计算出来，这样就可以减少复杂度。

定义 dp[i+1][j]，用前i种数加和得到j时第i种数最多能剩余多少个（不能加和得到i的情况下为-1）。

按照如上所述的递推关系，这样如果前i-1个数加和能得到j的话，第i个数就可以留下Mi个。此外，前i种数加和出j-Ai时第i种数还剩下k（k>0）德华，用这i种数加和j时第i种数就能剩下k-1个。由此我们能得到如下递推：

dp[i+1][j]=Mi; (dp[i][j]>=0)

dp[i+1][j]=-1; (j<Ai或者dp[i+1][j-Ai]<=0)

dp[I+1][j]=dp[I+1][j-Ai]-1; (其他)

这样，只要看最终结果是否满足dp[n][K]>=0就知道答案啦。

#include
    
     #include
     
      #include
      
       using namespace std;int n,K;int a[100],m[100];///a表示数字大小，m表示这个数字的个数bool dp[100];///dp数组void solve(){    memset(dp,-1,sizeof(dp));    dp[0]=0;    for(int i=0; i
       
        =0)///如果能组成数字j的话，                dp[j]=m[i];            else  if(j
        
         <=0)                dp[j]=-1;            else                dp[j]=dp[j-a[i]]-1;        }    if(dp[K]>=0)        printf("Yes\n");    else        printf("No\n");}int main(){    scanf("%d",&n);    for(int i=0; i