题目大意: 输入 n, 代表有 n 种数, 接下来 n 个数代表 n 种数, 再接下来 n 个数代表每种数有多少个, 在输入 K, 代表用这些数要加成的和
问你是否能加为 K, 能输出 yes, 不能输出 no
这是一个典型的多重背包问题, 可以用 dp 来求解,. 但是如何定义递推关系会影响到最终的复杂度, 首先我们先看一下如下定义:
dp[i+1][j];= 用前 i 种数能否加成和为 j
为了用前 i 种数加成 j, 也就需要能用前 i-1 种数字加成 j,j-a[i],...,j-mi*a[i], 中的某一种, 由此我们可以定义如下递推关系
dp[i+1][j]=(0<=k<=mi, 且 k*a[i]<=j 时, 存在使 dp[i][j-k*a[i]] 为真的 k;
看代码
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<cmath>
- #include<math.h>
- #include<algorithm>
- #include<set>
- #include<queue>
- typedef long long ll;
- using namespace std;
- const ll mod=1e9+7;
- #define INF 0x3f3f3f
- bool dp[110][100050];
- int main()
- {
- memset(dp,false,sizeof(dp));
- dp[0][0]=true;// 赋初值
- int n,s;
- int a[100050],b[100050];
- cin>>n;
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- for(int i=0;i<n;i++)
- cin>>b[i];
- cin>>s;
- //for(int i=0;i<n;i++)
- // cout<<a[i]<<' '<<b[i]<<endl;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<=s;j++)
- {
- for(int k=0;k<=b[i]&&k*a[i]<=j;k++)
- {
- dp[i+1][j]|=dp[i][j-k*a[i]];// 注意这里的或运算, 代表有一个为真则为真
- }
- }
- }
- //for(int i=0;i<=s;i++)
- // cout<<dp[n][i]<<' ';
- if(dp[n][s])
- cout<<"yes"<<endl;
- else
- cout<<"no"<<endl;
- return 0;
- }
上面这个算法的复杂度是比较大, 并不够好. 一般用 dp 求取 bool 结果的话会有不少浪费, 同样的复杂度通常能获得更多的信息
在这个问题中, 我们不光求出能否得到目标的和数, 同时把得到时 a[i] 这个数还剩多少个计算出来, 这样就可以减少复杂度
dp[i+][j]:= 用前 i 种数加和得到 j 时, 第 i 种数还剩多少个 (不能加的情况为 - 1)
按照如上所述的递推关系, 这样如果前 i-1 个数加能得到 j 的话, 第 i 个数就可以留下 b[i] 个了, 此外, 前 i 种数加和出 j-a[i] 时第 i 种数还剩 k(k>0) 个的话
, 用这 i 种数加和为 j 时就能剩 k-1 个了, 由此我们可以得出如下递推式:
- dp[i+1][j]=b[i] (dp[i][j]>=0)
- dp[i+1][j]=-1 (j<a[i]||dp[i_1][j-a[i]]<=0)
- dp[i+1][j]=dp[i+1][j-a[i]]-1 (其它)
看代码
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<cmath>
- #include<math.h>
- #include<algorithm>
- #include<set>
- #include<queue>
- typedef long long ll;
- using namespace std;
- const ll mod=1e9+7;
- #define INF 0x3f3f3f
- int dp[110][100050];
- int main()
- {
- memset(dp,-1,sizeof(dp));
- dp[0][0]=0;// 赋初值
- int n,s;
- int a[100050],b[100050];
- cin>>n;
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- for(int i=0;i<n;i++)
- cin>>b[i];
- cin>>s;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<=s;j++)
- {
- if(dp[i][j]>=0)
- dp[i+1][j]=b[i];
- else if(j<a[i]||dp[i+1][j-a[i]]<=0)
- dp[i+1][j]=-1;
- else
- dp[i+1][j]=dp[i+1][j-a[i]]-1;
- }
- }
- if(dp[n][s]>=0)
- cout<<"yes"<<endl;
- else
- cout<<"no"<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2685881.html