搜索专题(入门到入坑
算法1
(记忆化搜索) $O(n^2)$
本题需要注意的点如下:
第一,本题的数据偏大,所以需要运用记忆化搜索,在状态相同时直接返回。
第二,需要注意题目中的表达,物品的总体积不超过背包容量
。
第三,记得用 朴素算法 求最大价值,便于给背包划分阶段,降低枚举时间复杂度。
以下是对本题要点的解决:
第一,若将背包中的状态看成一棵 最短路树,则可以在这棵树的节点上同时保存 到达这个节点的方案,
符合 记忆化搜索 的要求,可以 直接取用。
第二,不超过 即 至多,意思为 容纳了体积小于背包容量的方案,解决方法有二:
一、同时搜索 价值相等、体积偏小 的方案,最后累计。
二、将背包取前 $0$ 个物品,体积不超过 $V$ 的所有状态的 方案数 置为 $1$,从而在搜索时钻空子,变相解决。
第三,如果不用 朴素算法,就很难确定所选物品 是否使用,到那时,就只能在计算最大价值的同时用 $Dp$ 计算了。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int f[N][N], g[N][N];
int dfs(int u, int c)
{
if (!u) return g[u][c] = 1;
if (g[u][c]) return g[u][c];
if (f[u][c] == f[u - 1][c])
g[u][c] = (g[u][c] + dfs(u - 1, c)) % mod;
if (c >= v[u] && f[u - 1][c - v[u]] + w[u] == f[u][c])
g[u][c] = (g[u][c] + dfs(u - 1, c - v[u])) % mod;
return g[u][c];
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d %d", &v[i], &w[i]);
for (int i = 1; i <= n; ++ i)
for (int j = 0; j <= m; ++ j)
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
printf("%d", dfs(n, m));
}
算法2
(Dp) $O(n^2)$
Dp 有什么可说的?
划一下阶段就可以了。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1010, mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int f[M], g[M];
int main()
{
scanf("%d %d", &n, &m);
memset(f, -0x3f, sizeof f);
f[0] = 0;
g[0] = 1;
for (int i = 1; i <= n; i ++ )
{
scanf("%d %d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
{
int maxv = max(f[j], f[j - v[i]] + w[i]);
int cnt = 0;
if (maxv == f[j]) cnt += g[j];
if (maxv == f[j - v[i]] + w[i]) cnt += g[j - v[i]];
g[j] = cnt % mod;
f[j] = maxv;
}
int res = 0;
for (int i = 0; i <= m; i ++ ) res = max(res, f[i]);
int cnt = 0;
for (int i = 0; i <= m; i ++ )
{
if (res == f[i])
{
cnt = (cnt + g[i]) % mod;
}
}
printf("%d", cnt);
}