AKSZ-动态规划
2024-06-30 16:22:09
发布于:广东
动态规划
其思想与分治法类似,是将待求解问题分为若干个小问题
通过局部最优求出全局最优
动态规划类问题主要的求解步骤:
- 划分阶段 斐波那契数列的每一项作为一个阶段
- 确定状态 第项的值用第位表示
- 确定决策并写出状态转移方程式 每一项的值都是前两项的和
结尾法:就表示以下标结尾的答案
性质
- 最优化原理:(最优子结构)
- 如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理
- 无后效性:
- 即某一阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
- 子问题重叠:
- 即子问题之间是不独立的,一个子问题在下一阶段决策中可能多次被使用到。(该性质并不知动态规划适用的必要条件,但是如果没有这条性质,动态规划算法问题同其他算法相比就不具备优势)
前缀法
表示 处理完毕的结果, 就是答案
有向无环图
背包
0/1背包
想象一个容量为的背包,你需要在个物品中选择一些物品转入,每个物品只有装/不装两个状态,并且每个物品占用空间为,价值为,求不超过容量能装进物品的最大价值
我们设表示在前个物品中已经选好了最佳方案,并且容量不超过时,所能获取的最大值
对于物品,如果选择不装入,则有(继承之前的状态)
如歌选择装入,则有(表示拿这个物品,占用对应背包空间,并且获取对应价值)
两者取最大,则有
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int v[maxn], w[maxn], dp[maxn][maxn];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t, m;
cin >> t >> m;
for(int i = 1; i <= m; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= m; i++){
for(int j = t; j >= 0; j--){
if(j >= v[i])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
cout << dp[m][t];
return 0;
}
滚动数组
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int v[maxn], w[maxn], dp[2][maxn];
int now = 0, last = 1; //now是当前行,last是上一行
int t, m;
void solve(){
for(int i = 1; i <= m; i++){
now ^= 1; last ^= 1;
for(int j = t; j >= 0; j--){
if(j >= v[i]) dp[now][j] = max(dp[last][j], dp[last][j - v[i]] + w[i]);
else dp[now][j] = dp[last][j];
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t >> m;
for(int i = 1; i <= m; i++) cin >> v[i] >> w[i];
solve();
cout << dp[now][t];
return 0;
}
压缩为1维
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int v[maxn], w[maxn], dp[maxn];
int t, m;
void solve(){
for(int i = 1; i <= m; i++)
for(int j = t; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t >> m;
for(int i = 1; i <= m; i++) cin >> v[i] >> w[i];
solve();
cout << dp[t];
return 0;
}
无限背包
想象一个容量为的背包,你需要在个物品中选择一些物品转入,每个物品可以任意选个数,并且每个物品占用空间为,价值为,求不超过容量能装进物品的最大价值
我们设表示在前个物品中已经选好了最佳方案,并且容量不超过时,所能获取的最大值
对于物品,如果选择不装入,则有(继承之前的状态)
如歌选择装入,则有(表示拿这个物品,占用对应背包空间,并且获取对应价值)
两者取最大,则有(注意j的循环一定要从小到大)
一维
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
const int maxn2 = 1e4+5;
long long v[maxn2], w[maxn2], dp[maxn];
int t, m;
void solve(){
for(int i = 1; i <= m; i++)
for(int j = v[i]; j <= t; j++)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t >> m;
for(int i = 1; i <= m; i++) cin >> v[i] >> w[i];
solve();
cout << dp[t];
return 0;
}
任务
- 完成题目时间 黄题20min 绿题40min 蓝题100min
- 手搓3组数据
- 每次提交WA之后 记录WA的原因
这里空空如也
有帮助,赞一个