01背包
抽象出来是有n种物品，每种物品只可以选一个或则零个
如果爆搜的话会是\(2^n\)，但利用\(dp\)可以减少不必要的讨论
模板
AcWing 2. 01背包问题 - AcWing
没什么好分析的，主要是二维向一维的优化，先看看朴素版本
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(j < v[i])
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
这里我们可以发现，每次更新\(f[i][j]\)的时候我们只利用到了上一层循环的值，换而言之在上一层之前的值没有意义，
所以我们可以利用滚动数组把二维优化为一维
要注意\(01\)背包的优化要反向遍历，因为假设我们从前往后遍历的话
$ f[i][j]$$=$ \(f[i-1][j]\)这项没有问题，但是当进行到\(f[i-1][j-v]+w\)的时候，利用的已经是先前更新过的这一层循环的值了
因此反向遍历可以避免这一点
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int v,w;scanf("%d%d",&v,&w);
for(int j=m;j>=v;j--)
f[j]=max(f[j],f[j-v]+w);
}
cout<<f[m];
}
例题
278. 数字组合 - AcWing题库
题意很简单，从n个数字里选出总和恰好为\(m\)的总方案数
定义\(f[i][j]\)为从前\(i\)个物品里面选，总和恰好为\(j\)的方案数
状态划分为选择\(i\)与不选择\(i\)，转移方程就显而易见了
\[f[i][j]=f[i-1][j]+f[i-1][j-a[i]] \]#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1e4+10;
int a[N];
int f[N][M];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n;i++)f[i][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=a[i])f[i][j]+=f[i-1][j-a[i]];
}
}
cout<<f[n][m];
}
优化成一维，更新用上一层循环，所以是反向遍历
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1e4+10;
int f[M];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
f[0]=1;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
for(int j=m;j>=x;j--)
{
f[j]+=f[j-x];
}
}
cout<<f[m];
}
上一题的扩展
Problem - D - Codeforces
有\(n\)种球，每种有若干个，每种球选或者不选，有\(2^n\)种选法
定义每种选法的\(value\)为把所选的每个球分在容量为\(2\)的组中，每组的颜色不可以相同的最小分法
假设选则的\(j\)种的球总和为\(sum\),最大值为\(mx\)
此种选法的\(vlaue\)为\(max(ceil(sum/2),mx)\)
如何使得可以遍历到每一种情况呢，可以这样考虑
用\(dp[i-1][j]\)表示从前\(i-1\)个物品中选，总和恰好等于\(j\)的选法，然后再选择\(a[i]\)
因为除了什么都不选之外，每种选法都是至少要选择一个\(a[i]\)的
从前往后遍历，固定一个a[i],考虑在前\(i-1\)个物品里选择再加上\(a[i]\)的选法，便是不重不漏的
为了方便计算，可以把数组先升序排序
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
const int M=998244353;
long long dp[N][N];
int a[N];
int n;
void solve()
{
dp[0][0]=1;
scanf("%d",&n);
int ans=0,m=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);m+=a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if((j+1+a[i])/2>=a[i])ans=(ans+(j+a[i]+1LL)/2*dp[i-1][j])%M;
else ans=(ans+1LL*a[i]*dp[i-1][j])%M;
dp[i][j]=dp[i-1][j];
if(j>=a[i])dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]])%M;
}
}
cout<<ans<<endl;
}
int main()
{
int t=1;
while(t--)solve();
}