首先那必须是
背包问题
01背包
朴素01
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
// f[i][j]是指
// 1)只能取(不一定都要取)前i个物品,
// 2)占用背包体积不超过j,
// 时的最大价值
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
{
// 不取第i个物体,那么f[i][j] = f[i-1][j]
f[i][j] = f[i-1][j];
// 取(此时价值是f[i-1][j-v[i]]+w[i]),那么首先要满足装得下它
// 并且取它价值更大
if (j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
}
cout << f[n][m] << endl;
return 0;
}
浅压一维
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
// About倒序原因:
// 二维时的更新方式:f[i][j]=max(f[i - 1][j] ,f[i - 1][j - v[i]] + w[i]);
// 1)对于每次循环的下一组i,只会用到i-1来更新当前值,不会用到i-2及之前值。
// 于是可以在这次更新的时候,将原来的覆盖掉,反正以后也用不到。
// 所以只需用一维数组,直接覆盖之前的就行了。
// 2)对于每次j的更新,只需用到之前i-1时的j或者j-v[i]。
// 同时,为了防止串着改,改成从后往前循环。
//(如果从前往后更新的话,前面的更新过之后,会接着使用新的前面值更新后面的值
// 这样就不能保证是用原来i-1的数组来更新i的了)
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j-v[i]]+w[i]);
cout << f[m] << endl;
return 0;
}
完全背包
过不了的朴素(TLE
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
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 = 0; j <= m; j++)
for (int k = 0; k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
cout << f[n][m];
return 0;
}
曲线救国2.0版本
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
// 注意与01不同的地方:
// 1)正着循环
// 2)呼应下文
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i-1][j];
// 呼应上文:2)f[i][j-v[i]]+w[i]中f第一维是i而非i-1
if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
}
cout << f[n][m];
return 0;
}
一维数组终极3.0版
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
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 = v[i]; j <= m; j++)
f[j] = max(f[j], f[j-v[i]] + w[i]);
cout << f[m];
return 0;
}
多重背包
朴素(数据范围小,或许可以过
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= s[i] && k*v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
cout << f[n][m];
return 0;
}
很酷的优化方式
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
// 此处1000 * log2000, 向上取整数N得12000
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
cin >> n >> m;
int cnt = 0;
while (n--)
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while (k <= s)
{
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k <<= 1;
}
if (s > 0)
{
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
// 本质就是转成01背包做了
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j-v[i]] + w[i]);
cout << f[m];
return 0;
}
分组背包
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
for (int j = 0; j < s[i]; j++)
cin >> v[i][j] >> w[i][j];
}
// 注意j倒序循环
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 0; k < s[i]; k++)
if (v[i][k] <= j)
f[j] = max(f[j], f[j-v[i][k]]+w[i][k]);
cout << f[m];
return 0;
}
其他
线性DP
较易,略
状态压缩DP
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
// bug1号,注意此处第二维是M(并且要注意开long long
long long f[N][M];
bool st[M];
int main()
{
// 高级写法get
while (cin >> n >> m, n || m)
{
// 预处理出对于每种i < 1<<n,是否合理
// 合理即:连续的0的个数都为偶数
// 这样才可以放一个竖着的块块
for (int i = 0; i < 1 << n; i++)
{
// i的二进制一段连续的0的个数
int cnt = 0;
// 先默认是合理的
st[i] = true;
for (int j = 0; j < n; j++)
// i二进制的第j位是1(也就是说前面的一段0结束了
if (i >> j & 1)
{
// 个数是奇数,故不合理
if (cnt & 1) st[i] = false;
// 归零,为统计下一段0的个数做准备
cnt = 0;
}
else cnt++; // 0的个数++
// 循环结束,最后一位若不是1,要盘点一下最后一段0的个数情况
if (cnt & 1) st[i] = false;
}
// 清掉上一笔数据留下的
memset(f, 0, sizeof(f));
// 只有一种
f[0][0] = 1;
for (int i = 1; i <= m; i++) // 循环m列(*!*:实际棋盘是第0列到第m-1列,要循环到m
for (int j = 0; j < 1 << n; j++) // 本列的情况为j
for (int k = 0; k < 1 << n; k++) // 上一列的情况为k
// 合理(第一个条件:没有重叠;第二个:没有奇数的竖空
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i-1][k];
// bug2号:!!!注意⚠️:这里是lld!否则白开longlong见祖宗
printf("%lld\n", f[m][0]);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> w[i][j];
memset(f, 0x3f, sizeof f); // 初始化为无穷大
f[1][0] = 0; // 因为零是起点
// a mini 优化:题目说起点一定是0,所以i一定是奇数
for (int i = 1; i < 1 << n; i += 2)
for (int j = 0; j < n; j++) // j表示走到哪一个点
if (i >> j & 1)
for (int k = 0; k < n; k++) // k表示走到j这个点的之前一步的终点
if (i >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
cout << f[(1 << n) - 1][n - 1]; // 表示所有点都走过了,且终点是n-1的最短距离
// 注意位运算优先级低,要加括号
return 0;
}
树形DP
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 6010;
int n;
int h[N], e[N], ne[N], idx; // 用来模拟建一个树
int happy[N];
int f[N][2];
bool has_fa[N]; // 判断当前节点是否有父节点
void add(int a, int b) // 把a插入树中
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++ ;
}
void dfs(int u)
{
f[u][1] = happy[u]; //如果选当前节点u,就可以把f[u][1]先加上他的高兴度
// ~i 酷
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][1] += f[j][0]; // 选u,所以不能选孩子们(j就是一个孩子
f[u][0] += max(f[j][0], f[j][1]); // 不选u,孩子j可选可不选,哪种更快乐就选哪种
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &happy[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(b, a); // 把a加到b后面
has_fa[a] = true; // 说明a有上司
}
int root = 1; // 用于找根节点
while (has_fa[root]) root++; // 找根节点
dfs(root);
// 输出不选根节点与选根节点中更大的那个
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}
记忆化搜索
还是递归的,只是记忆化了优化了罢了