标签：分组背包 完全 amp 二进制 进制 线性dp win ons class
动态规划
背包问题
状态表示
1.集合：所有只考虑前i个物品，且总体积不大于j的所有选法
2.属性：MAX
2.1 去掉k个物品i
2.2 求MAX，f【i - 1】【j - k * v】
2.3 再加回来k个物品i
状态计算：集合的划分
1. 0-1背包（Acwing-2）
朴素做法
#include
#include
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 > v[i] >> w[i];
for (int i = 1; i = v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout
一位数组优化
#include
#include
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 > v[i] >> w[i];
for (int i = 1; i = v[i]; --j) {
f[j] = max(f[j], f[j - v[i]]+ w[i]);
}
}
cout
2.完全背包（Acwing-3）
朴素做法
#include
#include
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 > v[i] >> w[i];
for (int i = 1; i
优化做法
#include
#include
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 > v[i] >> w[i];
for (int i = 1; i = v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
}
cout
终极做法
#include
#include
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 > v[i] >> w[i];
for (int i = 1; i
3.多重背包-I（Acwing）
朴素做法
#include
#include
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 > v[i] >> w[i] >> s[i];
for (int i = 1; i
二进制优化
#include
#include
using namespace std;
const int N = 25000, M = 2000;
int n, m, cnt = 0;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i > a >> b >> s;
while (k 0) {
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for (int i = 1; i = v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout
分组背包（Acwing-9）
#include
#include
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 > s[i];
for (int j = 0; j > v[i][j] >> w[i][j];
}
}
for (int i = 1;i = 0; --j) {
for (int k = 0; k
线性DP
数字三角形（Acwing-898）
#include
using namespace std;
const int N = 510;
int n, INF = 1e9;
int a[N][N], f[N][N];
int main() {
cin >> n;
for (int i = 1; i > a[i][j];
}
}
for (int i = 0; i
最长上升子序列（Acwing-895）
#include
using namespace std;
const int N = 1010, INF = 1e9;
int n, a[N], f[N];
int main() {
cin >> n;
for (int i = 1; i > a[i];
for (int i = 1; i
最长上升子序列-II（Acwing-896）
#include
using namespace std;
const int N = 100010;
int n, a[N], f[N];
int main() {
cin >> n;
for (int i = 0; i > a[i];
int len = 0;
f[0] = -2e9;
for (int i = 0; i > 1;
if (f[mid]
最长公共子序列（Acwing-897）
#include
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main () {
cin >> n >> m;
scanf("%s%s", a + 1, b + 1);
for (int i = 1; i
最短编辑距离（Acwing-902）
#include
#include
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
scanf("%d%s", &n, a + 1);
scanf("%d%s", &m, b + 1);
for (int i = 0; i
区间DP
石子合并（Acwing-282）
#include
#include
using namespace std;
const int N = 310;
int n, s[N], f[N][N];
int main() {
cin >> n;
for (int i = 1;i > s[i];
for (int i = 1;i
Acwing------动态规划
标签：分组背包 完全 amp 二进制 进制 线性dp win ons class
原文地址：https://www.cnblogs.com/clown9804/p/12426404.html