$Acwing$算法进阶学习$dp$专题:背包问题
背包问题:
- 背包问题是线性$dp$一类非常特别的模型。
- 01背包:物品只能用一次。
- 完全背包:物品可以用无限次。
- 多重背包:每个物品都有限制次数。
- 分组背包:每组只能选一个,有若干组。
例题1acw278:数字组合
题意:
- 给定$n$个数字,从中选出若干个数字使他们的和为$m$,问有多少种方案。
思路:
- 01背包问题。
-
$a_i$看成是体积,$m$看成是背包容量,$f(j)$代表和为$j$有多少方案。
-
有转移方程$f(j)+=f(j-a(i))$.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
const int maxm = 1e4+10;
int a[maxn], n, m, f[maxn];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
f[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = m; j >= a[i]; j--)
f[j] += f[j-a[i]];
cout << f[m] << endl;
return 0;
}
例题2acw279:自然数拆分
题意
- 给一个自然数$n$,要求把$n$拆分成若干整数相加的形式,参加的运算的数字可以重复。
- 求方案数。
思路
- 完全背包,因为一个数字可以用很多次。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e3+10;
const ll mod = 2147483648;
ll f[maxn], n;
int main()
{
cin >> n;
f[0] = 1;
for(int i = 1; i <= n-1; i++)
for(int j = i; j <= n; j++)
f[j] = (f[j]+f[j-i])%mod;
f[n] = (f[n]+mod)%mod;
cout << f[n] << endl;
return 0;
}
例题3acw280:陪审团
题意
- 有$n$个人,每一个人有两个分数$p(i),d(i)$,选$m$人,求方案使$|d-p|$最小,多种合法方案的话选择$d+p$最大的一组。
数据范围
- $n\leq 200,m\leq 20, p,d\leq 20$
思路
- 选出来的人很少,而且分数的差也较低,所以可以先按照差值来挑选方案,也就是$-400$到$+400$分值段。
- 之后我们就可以先去差值为$0$的方案找,如果没有就去看$1,-1$有没有这样的方案,…
- 所以定义$f(i,j,k)$表示前$i$个人中选择$j$个人并且差值为$k$的$p+d$的最大值。
- 对于每个人只有pick或ban的可能,所以这是一个01背包。
- 转移方程$:f(i,j,k)=max\{f(i-1,j,k),f(i,j-1,k-(p_i-d_i))+(p_i+d_i)\}$。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
const int maxm = 800 + 10;
const int base = 400;
int n, m;
int f[maxn][25][maxm];
int p[maxn], d[maxn];
int ans[maxn];
int main()
{
int cnt = 1;
while(scanf("%d%d", &n, &m))
{
if(n==0 && m==0) break;
for(int i = 1; i <= n; i++)
scanf("%d%d", &p[i], &d[i]);
memset(f, -0x3f, sizeof(f));
f[0][0][base] = 0;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k < maxm; k++)
{
f[i][j][k] = f[i-1][j][k];
int tmp = k-(p[i]-d[i]);
if(tmp < 0 || tmp >= maxm) continue;
if(j < 1) continue;
f[i][j][k] = max(f[i][j][k], f[i-1][j-1][tmp]+p[i]+d[i]);
}
int v = 0;
while(f[n][m][base-v] < 0 && f[n][m][base+v] < 0) v++;
if(f[n][m][base-v] > f[n][m][base+v]) v = base - v;
else v = base + v;
int i = n, j = m, k = v, tot = 0;
while(j)
{
if(f[i][j][k] == f[i-1][j][k])// 可以不选第i个人
i--;
else
{
ans[++tot] = i; //选第i个人
k -= (p[i]-d[i]);
i--, j--;
}
}
int ansp = 0, ansd = 0;
for(int i = 1; i <= tot; i++)
{
ansp += p[ans[i]];
ansd += d[ans[i]];
}
printf("Jury #%d\n", cnt++);
printf("Best jury has value %d for prosecution and value %d for defence:\n", ansp, ansd);
for (int i = 1; i <= tot; i ++ )
printf(" %d", ans[i]);
puts(""); puts("");
}
return 0;
}
例题4acw281:硬币
题意
- 给$n$种硬币,第$i$种面值为$a_i$,数量为$c_i$个,问从中选若干硬币,问$1$到$m$区间能被拼成的面值有多少个。
数据范围
- $n\leq 100, m\leq10^5,a_i\leq10^5,c_i\leq10^3$。
思路
- 多重背包应该是没问题的。
- 多重背包直接写是不行的,二进制优化一下其实危险也挺大的,单调队列优化大概能控制在$10^7$的计算。
- 但这里需要注意的一点是:
- 本题仅关注“可行性”,不关注“最优性”。
- 也就是我们只关注他能不能凑出来。
- 设$f(i,j)$表示在前$i$个物品,面值为$j$是否能被拼凑出来。
- 对与第$i$种硬币能否凑成$j$面值只有两种可能。
- 已经凑好了。
- $j-a(i)$凑好了,然后$j$从$j-a(i)$转移过来。
- 设$vis(j)$表示在第$i$个状态时,凑成$j$面值至少要用多少枚$i$硬币。
- 那么转移的时候就是尽可能的用前面凑出来的状态,这样第$i$种硬币就可以达到“至少”这种可能。
- 那也就是说,对于第$i$个状态,如果他的$j==true$,那么就可以不用第$i$种硬币。
- 如果对于$j$不是$true$,但是$f(j-a(i))==true$且还有足够的硬币的时候,就可以转移。
- 详见代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 10;
const int maxm = 1e5 + 10;
bool f[maxm];
int n, m;
int a[maxn], c[maxn];
int vis[maxm];
int main()
{
while(cin >> n >> m)
{
if(n == 0 && m == 0) break;
memset(f, 0, sizeof(f));
f[0] = true;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++) vis[j] = 0;
for(int j = a[i]; j <= m; j++)
if(!f[j] && f[j-a[i]] && vis[j-a[i]] < c[i]) {
f[j] = true;
vis[j] = vis[j-a[i]]+1;
}
} int ans = 0;
for(int i = 1; i <= m; i++)
ans += f[i];
cout << ans << endl;
}
return 0;
}
太棒了
%%