AcWing算法提高课——动态规划
背包模型
宠物小精灵之收服
知识点
解题思路
- 本题经过分析：
- 花费1：精灵球数量
- 花费2：皮卡丘体力值
- 价值：小精灵的数量
双重价值背包
- 状态表示：
-
f[i][j][k]表示所有只从第i个物品中选，且花费1不超过j，花费2不超过k。
-
- 状态计算：
f[i][j][k] = max(f[i][j][k], f[i - 1][j - v1[i]][k - v2[i]])
实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 510;
int n, V1, V2;
int f[N][M];
int main(){
cin >> V1 >> V2 >> n;
for(int i = 1; i <= n; i ++){
int v1, v2;
cin >> v1 >> v2;
for(int j = V1; j >= v1; j --)
for(int k = V2; k > v2; k --)
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
int k = V2;
while(k > 0 && f[V1][k] == f[V1][V2])
k --;
cout << f[V1][V2] << " " << V2 - k << endl;
return 0;
}
数字组合
实现代码
// 状态表示f[i][j]
// 集合表示：遍历到第i个数，和为j的方案数
// 属性：数量
// 状态计算
// f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]]
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int f[N][M];
int a[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> a[i];
f[i][0] = 1;
}
f[0][0] = 1;
int res = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
f[i][j] = f[i - 1][j];
if(j >= a[i])
f[i][j] += f[i - 1][j - a[i]];
}
}
cout << f[n][m] << endl;
return 0;
}
买书
知识点
解题思路
- 动态规划:
- 状态表示
- 集合：所有只从前i个物品中选，并且总体积恰好是j的方案数
- 属性：Count
- 状态计算：
f[i][j] = f[i - 1][j]f[i][j] += f[i - 1][j - v*1] + f[i - 1][j - v*2] + ...
- 状态表示
实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[N];
int main(){
int m;
cin >> m;
f[0] = 1;
for(int i = 1; i <= 4; i ++){
for(int j = 0; j <= m; j ++){
if(j >= v[i])
f[j] += f[j - v[i]];
}
}
cout << f[m] << endl;
return 0;
}
货币系统
实现代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3010;
LL f[N], w[N];
int n, m;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> w[i];
f[0] = 1;
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= m; j ++)
if(j >= w[i])
f[j] += f[j - w[i]];
cout << f[m] << endl;
return 0;
}
货币系统(难)
知识点
- 完全背包问题
解题思路
- 状态表示f[i][j]
- 集合：用前i种类硬币，组成数值为j的硬币
- 属性：能够表示出数值为j的硬币，bool
- 状态计算
- 可以分为若干个集合
- 用0个第i类硬币
- 用1个第i类硬币
- …
- 用 k 个第i类硬币
- 可以分为若干个集合
- 进行循环时，首先判断该硬币是否已经能表示，如果已经能被表示，则跳过
实现代码
// 状态表示f[i][j]
// 集合：用前i种类硬币，组成数值为j的硬币
// 属性：能够表示出数值为j的硬币，bool
// 状态计算
// 可以分为若干个集合
// 用0个第i类硬币
// 用1个第i类硬币
// 。。。
// 用 k 个第i类硬币
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 25010;
int tt = 0;
int a[N];
bool f[M];
int main(){
cin >> tt;
while(tt --){
memset(f, 0, sizeof f);
memset(a, 0, sizeof a);
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
int m = a[n];
f[0] = 1;
int res = 0;
for(int i = 1; i <= n; i ++){
if(f[a[i]])
continue;
res ++;
for(int j = a[i]; j <= m; j ++){
f[j] |= f[j - a[i]];
}
}
cout << res << endl;
}
return 0;
}
Enjoy Reading This Article?
Here are some more articles you might like to read next: