这周主要还是学习线性dp，但是因为考试这周练习确实不多。还是把一些练习和基本的背包问题整理一下。
01背包一维优化和记忆化搜索最朴素的写法是把物品数放入递推过程中一起递推了，虽然一维优化后思路上仍然如此，但是没必要在在dp数组里加入物品数。
我们可以把物品数优化，让体积从0-v每层外循环刷新一次dp数组（当前体积的最优解），但即使是把物品数优化dp数组化为一维，外层循环一样起到了枚举每一个背包体积的对应物品数的状态。直白点说，我们还是比较的同一体积下随着物品数增加最优解对应的变化，如果当前的体积下的最优解比下一次外循环（物品数变化）大，我们就更新对应体积的dp数组值（最优解）
但是要注意，一维优化的思路不是很直观
这里的的dp[i]是原值，这个 dp[i-vb[j] 指的是上一个物品数下对应的该体积的最优解。也就是上一层外循环的对应体积dp数组值。所以重点就在这，我们要怎么才能让下一层外循环（物品数）的dp值跟上一层比较？不能从前往后枚举背包体积了，因为从前往后枚举体积，下一层外循环会从前往后覆盖原来的dp数组值，也就是说如果从前往后递推会覆盖上一层的dp数组值，导致没法与之前的最优解取最值。所以这里的解决方案是从后往前枚举体积。
#include#include #include #include #include #include using namespace std; int vb[1000001] = { 0 }, w[1000001] = { 0 }, s[1000001] = { 0 }; int dp[100001] = { 0 }; int n, v; int main() { cin >> n >> v; int k = 0; for (int j = 1; j <= n; j++) cin >> vb[j] >> w[j]; for (int j = 1; j <= n; j++) {//物品数 for (int i = v; i >= vb[j]; i--) {//背包体积，从后往前逆向枚举 //保证可以用到上一层外循环的dp值 if (i - vb[j] >= 0) dp[i] = max(dp[i], dp[i - vb[j]] + w[j]); } } int ans = 0; for (int j = 0; j <= v; j++) ans = max(ans, dp[j]); cout << ans; return 0; }
记忆化搜索的本质就是dp。按常规的搜索思路，再用dp数组记录每次的状态
#include完全背包#include #include #include #include #include #include using namespace std; int object[1001] = { 0 }; int n, v; int vb[10001] = { 0 }, w[10001] = { 0 }; int mx = 0; int rec[10000][10000] = { 0 }; int dfs(int dep ,int vnow) {//dep为搜索深度，也就是当前有几个物品 int res=0; if (rec[dep][vnow] > 0) return rec[dep][vnow];//记忆数组已经记录过就输出 if (dep == n) return 0;//搜索终点,物品都搜完了拿不了，返回0 if (vnow - vb[dep] <0) res = dfs(dep + 1, vnow); //拿不了的 else if (vnow - vb[dep] >=0) res= max(dfs(dep + 1, vnow), dfs(dep + 1, vnow - vb[dep]) + w[dep]);//取每个路线的最大值 return rec[dep][vnow]=res;//记忆 } int main() { cin >> n >> v; for (int j = 0; j < n; j++) cin >> vb[j] >> w[j]; cout << dfs(0, v); }
我是这么理解完全背包的，对于每个体积，我每次都可以选最多当前物品数的物品。所以从中挑出选完直观物品，使价值最大物品即可。写成搜索的形式会更直观
//#include#include //#include #include #include #include #include #include using namespace std; int dp[10000] = { 0 }, vb[10001] = { 0 }, w[100001] = { 0 }; int main() { int n, v; cin >> n >> v; for (int j = 1; j <= n; j++) { cin >> vb[j] >>w[j]; } for (int j = 1; j <= v; j++) { for (int i = 1; i <=n; i++) { if (j - vb[i] < 0)continue; else dp[j] = max(dp[j - vb[i]] + w[i], dp[j]); } } cout << dp[v]; return 0; }
记忆化搜索
#include多重背包#include #include #include #include #include #include using namespace std; int object[1001] = { 0 }; int n, v; int vb[10001] = { 0 }, w[10001] = { 0 }; int mx = 0; int rec[10000] = { 0 }; int dfs(int vnow) {//dep为搜索深度，也就是当前有几个物品 //rec[vnow]已经初始化为0 ， //也就是说dfs返回的时候价值沿路的价值为0+沿路的所选物品价值 if (rec[vnow] != 0)return rec[vnow]; for (int j = 0; j < n; j++) {//枚举每一种物品 if(vnow>=vb[j]) rec[vnow] = max(dfs(vnow - vb[j]) + w[j], rec[vnow]); } return rec[vnow]; } int main() { cin >> n >> v; for (int j = 0; j < n; j++) cin >> vb[j] >> w[j]; cout << dfs( v); }
其实就是把选择物品变成了选择物品类，像01背包那样枚举每个类别选不选，再枚举选几件即可
所以同样可以一维优化
#include分组背包//#include #include #include #include #include #include using namespace std; int vb[100001] = { 0 }, w[100001] = { 0 }, s[100001] = { 0 }; int dp[10000] = { 0 }; int mx = 0; int n, v; int main() { cin >> n >> v; for (int j = 1; j <= n; j++) { cin >> vb[j] >> w[j] >> s[j]; } for (int j = 1; j <= n; j++) { for (int i = v; i >=0; i--) { for (int k = 0; k <= s[j]; k++) { if (i - vb[j] * k >= 0) dp[i] = max(dp[i], dp[i-vb[j]*k]+w[j]*k); } } } cout << dp[v]; return 0; }
按我的理解，我认为分组背包其实就是同一种类内的物品不同的多重背包，所以和多重背包相似枚举组（种类），然后再枚举选择组内哪个物品使价值最大
但是存储相对麻烦，我采用邻接表的形式
#include#pragma warning (disable:4996); #define ll long long #define int ll #define mem(a,b) memset(a,b,sizeof(a)) #define endl 'n' using namespace std; const int N = 2e5 + 10; const int mod = 80112002; int T, n, m, k, q; int a, b, c; struct node { node(int a,int b):v(a),w(b){} int v,w; }; vector bag[N]; vector dp(N, 0); signed main() { //ios::sync_with_stdio(0); cout.tie(0); #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int v; cin >> n >> v; for (int j = 0; j <= n; j++) { cin >> k; for (int i = 1; i <= k; i++) { cin >> a >> b; bag[j].push_back({ a,b }); } } for (int j = 0; j < n; j++) { for (int i = v; i >= 0; i--) { for (int p = 0; p < bag[j].size();p++) { node now = bag[j][p]; if (i >= now.v) { dp[i] = max(dp[i - now.v] + now.w, dp[i]); } } } } cout << dp[v]; }
以上是比较基本，但是很重要的背包问题。接下来是本周的一些练习。
P3183 [HAOI2016]食物链 记忆化搜索（dp）本周就是求图内从入度为0的点（食物链底端）到出度为0的点（顶端）的路径条数。
dp主要记录的是，从该顶点为起点有几条可以到达出度为0的点。
采用搜索的方式遍历图找到底端到顶端的路径会更方便，所以使用记忆化搜索的方式
当能找到一条到顶端的路径时返回1，对每个子节点都遍历求和，即可得到当前起点的食物链条数
设i为入度为0的起点，j为i的子节点，dp表示到终点的路径条数。有状态转移
dp[i]+=dp[j]
#include#pragma warning (disable:4996); #define ll long long #define int ll #define mem(a,b) memset(a,b,sizeof(a)) #define endl 'n' using namespace std; const int N = 2e5 + 10; int T, n, m, k, q; int a, b, c; vector gra[N]; vector dp(N, 0); vector ind(N, 0),oud(N,0); inline int dfs(int now) { if (dp[now])return dp[now]; if (oud[now] == 0)return 1; int res = 0; for (auto& x : gra[now]) { res+=dfs(x); } return dp[now] = res; } signed main() { // ios::sync_with_stdio(0); cout.tie(0); #ifndef ONLINE_JUDGE //freopen("out.txt", "w", stdout); #endif cin >> n>>m; for (int j = 1; j <= m; j++) { scanf("%d%d", &a, &b); gra[a].emplace_back(b); ind[b]++; oud[a]++; } int ans = 0; for (int j = 1; j <= n; j++) { if(ind[j]==0&&oud[j]!=0) ans += dfs(j); } printf("%d", ans); }
213. 打家劫舍 II - 力扣（LeetCode）dp，状态讨论
如果要抢一个房间i，那么他的状态则有i-2转移来。如果不抢，则继承上一个房间的状态。状态转移
dp[x]=max(dp[x-2]+nums[i],dp[x-1])
这题的状态转移非常简单，但是这题首尾成环，一个比较简便的思路就是单独讨论起点和终点的状态。
如果第一个房间抢了，那么第n个房间就不管他了。其值继承dp[n-1]
所以我们从第1个房间计算到第n-1个房间即可。
如果第一个房间不抢，那么第n个房间可抢可不抢，所以放到动态规划过程里递推计算即可。
class Solution:
def r1(self,nums:list[int],s,e):
n=len(nums)
dp=[0 for _ in range(n+10)]
for x in range(s,e+1):
i=x-1
if x==1:
dp[x]=nums[i]
else:
dp[x]=max(dp[x-2]+nums[i],dp[x-1])
return dp[e]
def rob(self, nums: List[int]) -> int:
n=len(nums)
if n==1:
return nums[0]
return max(self.r1(nums,1,n-1),self.r1(nums,2,n))
