行业知识
【CSP】2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝
2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/深搜+剪枝2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝
- 2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝
- 动态规划思路
- 遇到的问题(补一些01背包的知识)
- 深搜+剪枝思路
- 动态规划完整代码
- ���搜完整代码
2022-09-2 何以包邮? 拐个弯的动态规划(01背包问题)/ 深搜+剪枝
这题由于其数据的量并不大我们可以有两种思路来解决这个问题。
动态规划思路
这道题其实得先想到的是动态规划,然后拼命的往上靠,或许才能想出来拐个弯。
01背包问题都是在不超过一定容量下,求最大价值是多少,然后我们就可以将重量当作价值,就可以求出在一定容量下,求最大的占用的容量是多少。但是这个题目时求超出一定容量下最小的容量占用是多少,此时我们就可以反着想。
题目让我们求出要选的书,我们其实也可以选出不选的书,然后剩下就是要选的书,总共的价钱减去不选的书的钱就是剩下的钱。所以这就转换成了01背包问题 容量为sum–x价值是a[i](重量)的01背包问题。
遇到的问题(补一些01背包的知识)
- 首先01背包问题大家可以在网上搜到很多资源,解释的也很好,这里就简要的写一下
01背包的状态转移方程
f i , j = m a x ( f i , j , f i , j − w i + v i ) f_{i,j}=max(f_{i,j},f_{i,j-w_i}+v_i) fi,j=max(fi,j,fi,j−wi+vi)
然后针对这个题目的状态转移方程就是
f i , j = m a x ( f i , j , f i , j − w i + w i ) f_{i,j}=max(f_{i,j},f_{i,j-w_i}+w_i) fi,j=max(fi,j,fi,j−wi+wi)
f i , j f_{i,j} fi,j代表的是从前i本书中选择,在不超过容量为j的情况下,最大的容量(价值)
- 实现过程中遇到了一些问题
第一个问题就是发现这个代码是错误的
for (int i = 1; i > x; for (int i = 1; i > a[i]; sum += a[i]; } for (int i = 1; i = 1; j--) { if (j >= a[i]) dp[j] = max(dp[j], dp[j - a[i]] + a[i]); } } cout > n >> x; for (int i = 0; i > a[i]; s += a[i]; } dfs(0, s); cout
下一篇:企业标准备案是啥要怎么办理