dp总结1
背包
01背包
一个旅行者有一个最多能用m公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn.若每种物品只有一件求旅行者能获得最大总价值。
dp[i][j]表示前i件物品,容量为j的背包能获得的最大价值
那么,很明显直接的可以得到,dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
dp[i - 1][j]意为不选择第i件物品,光是前i - 1件物品所能获得的最大价值
dp[i - 1][j - w[i]] + c[i]意为选择第i件物品所能获得的最大价值
1
2
3 for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);这个代码的时间和空间复杂的都是O(m * n),其中时间复杂度已经无法优化了,但是空间复杂的还可以优化到O(n)
1
2
3
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
1 | for (int i = 1; i <= n; i++) |
完全背包
设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。
注意上面代码的内层循环是从m到w[i],因为每个物品只能选一次,所以不能对后续选择造成影响,所以只能从m到w[i];然而现在是可以无限制选择,就是可以影响后续选择,所以只需要改一下内层循环的顺序就好了
1
2
3 for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
多重背包
有N种物品和一个容量为V的背包。第i ii种物品最多有p[i]件可用,每件费用是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
这里有一种很暴力的做法就是加上一重循环,从1遍历到p[i]
1
2
3
4 for (int i = 1; i <= n; i++)
for (int k = 0; k <= p[i]; k++)
for (int j = m; j >= w[i] * k; j--)
dp[j] = max(dp[j], dp[j - w[i] * k] + c[i] * k);
这种做法当然可以优化的,当我们进行了k=1和k=2之后紧接着就是k=3,可是k=3是冗余的,因为1和2的组合可以得到3,进行了k=4的循环后,5,6,7三次循环全是冗余的,因为1,2,4完全可以组合得到他们;同理我们只需要进行log(n)次循环就可以遍历0-p[i]所有的数了
1
2
3
4
5
6
7
8
9 for(int i = 1; i <= n; i++) {
int num = min(p[i], m / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = m; j >= w[i] * k; j--)
dp[j] = max(dp[j], dp[j - w[i] * k] + c[i] * k);
}
}
背包恰好装满
之前全是不超过背包最大容量,如果题目是恰好装满背包,其实就只需要在初始化dp的时候修改一下,dp[0] = 0,其他的位置全是负无穷, 用01背包举例
1
2
3
4
5
6 const int INF = 0x3f3f3f3f;
memset(dp, -INF, sizeof(dp));
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + c[i])
分组背包
有N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是v[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
例题
总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M≤15,N≤10。分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。
Input
第一行有两个数,第一个数是分公司数N,第二个数是设备台数M。接下来是一个N*M的矩阵,表明了第 I个公司分配 J台机器的盈利。
Output
第一行输出最大盈利值。接下来的N行,每行2个整数,分别为分公司编号以及分配的机器数
Sample Input
3 3
30 40 50
20 30 50
20 25 30Sample Output
70
1 1
2 1
3 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
const int N = 20;
int val[N][N], dp[N][N];
void Print(int n, int m) {
if (n == 0) return ;
int k = m;
for (int i = k; i >= 0; i--) {
if (dp[n][m] == dp[n - 1][m - i] + val[n][i]) {
Print(n - 1, m - i);
printf("%d %d\n", n, i);
return ;
}
}
}
int main () {
int n, m;
while (~scanf("%d%d", &n, &m)) {
memset(val, 0, sizeof val);
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &val[i][j]);
for (int k = 1; k <= n; k++)
for (int j = m; j >= 0; j--) {
for (int i = 0; i <= j; i++) {
if (dp[k][j] < dp[k - 1][j - i] + val[k][i])
dp[k][j] = dp[k - 1][j - i] + val[k][i];
}
}
printf("%d\n", dp[n][m]);
Print(n, m);
}
return 0;
}
最长XX子序列
最长公共子序列
求两个字符串的最长公共子序列
子序列:从原字符串选择某些字符,顺序不变连接,不要求位置连续
子串:从原字符串选择某些连续的字符,顺序不变连接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
const int N = 220;
int main () {
char s1[N], s2[N];
int a[N][N];
while (~scanf("%s%s", s1 + 1, s2 + 1)) {
memset(a, 0, sizeof a);
int len1 = strlen(s1 + 1);
int len2 = strlen(s2 + 1);
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i] == s2[j]) a[i][j] = a[i - 1][j - 1] + 1;
else a[i][j] = max(a[i - 1][j], a[i][j - 1]);
}
}
printf("%d\n", a[len1][len2]);
}
return 0;
}
最长上升子序列
ac代码
1 |
|
把城市左边按升序排好序之后,这个就是求最长上升子序列的题
ac代码
1 |
|
其他
ac代码
1 |
|