做网站公司长沙哪家好/百度搜索量最大的关键词

传送门

多重部分和问题：

有n种不同大小的数字ai，每种各mi个，判断是否可以从这些数字之中选出若干使得它们的和恰好为K

首先看这个定义：

dp[i+1][j]:=用前i种数字是否能加和成j，为了用前i种数字加和成j，也就需要用前i-1种数字加成j，j-ai，...，j-mi*ai中的某一种。由此得到递推关系：

dp[i+1][j]=(0<=k<=mi且k*aj<=j时存在使dp[i][j-k*ai]为真的k)

int n;//数列长度
int K;//目标和数
int a[MAXN];//值
int m[MAXN];//个数
bool dp[MAXN+1][MAXK+1];
void solve()
{dp[0][0]=true;for(int i=0;i<n;i++){for(int j=0;j<=K;j++){for(int k=0;k<=m[i]&&k*a[i]<=j;k++){dp[i+1][j]|=dp[i][j-k*a[i]];}}}if(dp[n][K]){printf("YES\n");}else{printf("NO\n");}
}

这个算法的复杂度是，这样并不好。一般用DP求取bool结果的话会有不少浪费，同样的复杂度通常能获得更多的信息。在这个问题中，不光求出能否得到目标的和数，同样把得到ai这个数还剩下多少个求出来，就可以减少复杂度。

dp[i+1][j]:=用前i种数加和得到j时第i种数最多能剩余多少个(不能加和得到j的情况下为-1)

按照如上所述定义递推关系，这样如果前i-1个数加和能得到j的话，第i个数就可以留下mi个。此外，前i种数加和出j-ai时第i种数还剩下k(k>0)的话，用这种数加和j时数就能剩下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就可以知道答案了

这个递推式可以在O(nK)时间内计算出结果，再将数组重复利用的

附上代码：

int dp[MAXK+1];
void solve()
{memset(dp,-1,sizeof(dp));dp[0]=0;for(int i=0;i<n;i++){for(int j=0;j<=K;j++){if(dp[j]>=0){dp[j]=m[i];}else if(j<a[i]||dp[j-a[i]]<=0){dp[j]=-1;}else{dp[j]=dp[j-a[i]]-1;}}}if(dp[K]>=0){printf("Yes\n");}else{printf("No\n");}
}

题解：

还有篇博文可以参考：传送门

附上代码：

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int maxn=100;
const int maxm=100001;int n,m,a[maxn],c[maxn],dp[maxm];int main()
{while(scanf("%d%d",&n,&m)!=EOF){if(!n){break;}memset(dp,-1,sizeof(dp));for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n;i++){scanf("%d",&c[i]);}dp[0]=0;for(int i=0;i<n;i++){for(int j=0;j<=m;j++){if(dp[j]>=0){dp[j]=c[i];}else if(j<a[i]){dp[j]=-1;}else{dp[j]=dp[j-a[i]]-1;}}}int num=0;for(int i=m;i>=1;i--){if(dp[i]>=0){num++;}}printf("%d\n",num);}return 0;
}