01背包问题 目录 1——问题概览 2——DP实现(状态转移方程推论) 3——对于01背包问题的优化 二维到一维 问题概览 难度：普及 题目：YBT1267 01背包问题(模版) 描述： 一个旅行者有一个最多能装MMM公斤的背包，现在有nnn件物品 它们的重量分别是W1，W2，...,WnW_1，W_2，...,W_nW1 ，W2 ，...,Wn ,它们的价值分别为C1,C2,...,CnC_1,C_2,...,C_nC1 ,C2 ,...,Cn 求旅行者能获得最大总价值。 DP实现(状态转移方程推论) 首先为什么要叫这为01背包问题？？？ 由题可得，对于任一物品只有拿取或者不拿这两种选择(对于一次选择，执行或不执行) 因此也就由"01"代表这个意思了，这是背包问题的root也是最简单的背包问题 如果用普通的搜索来解决，时间复杂度是O(2n)O(2^n)O(2n)，这简直惊为天人！！！ 思考下，我们可以把问题分阶段为取第iii件物品且容量为vvv时可获得的最大价值，从第111件商品与背包容量为111时开始往后递推，找到每一阶段的最大值，最终肯定能找到全局最优解，满足动态规划的最优子结构特点 因为前面i−1i-1i−1物品已经为最优了，所以只需要看放第iii个物品和不放第i个物品所获的价值哪个大 但放下也有前提条件，就是第iii个物品重量要小于当前背包容量vvv，不然你就算把背包掏空也塞不下...... 简易分析得以下结论 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ A.放不了：直接不放这个物品，最优解——放这个物品前的最优解 B.放得下： a.先清空背包，只放这个物品，再看看剩余容量能否装下之前的物品，最优解——这个物品的价值+背包剩余容量的最优解 b.不放这个物品，最优解——放这个物品前的最优解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 然后，a、b 情况进行比较，选出真正的最优解 设DP[i][v]DP[i][v]DP[i][v]为当操作物品为iii个,背包容量为vvv时所获最大价值 状态转移方程就是DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value) 注：i.weighti.weighti.weight指第iii件物品的重量 valuevaluevalue指第iii件物品的价值 代码实现如下 对于01背包问题的优化 二维到一维 其实对于01背包的时间已经到O(M∗N)O(M*N)O(M∗N)了，没法再优化了 但对于空间却可以进一步压缩 我们重新定义DP[v]DP[v]DP[v]为背包容量为vvv下所获的最大价值 根据我们上文的分析DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value) 其中DP[i−1][v]DP[i-1][v]DP[i−1][v]和DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]都是上一次操作时，容量为vvv和v−i.weightv-i.weightv−i.weight下所得最大价值 可知每一次的DP[i][v]DP[i][v]DP[i][v]都依赖上一轮的最大值 但是我们可以使用逆推来省去[i−1][i-1][i−1]的步骤，因为在一轮iii之后的i+1i+1i+1轮中DP[v]DP[v]DP[v]存储的都是上一次所能获得的最大值 这就使得DP[v−i.weight]DP[v-i.weight]DP[v−i.weight]代替了DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]的功能，并且压缩了空间 状态转移方程为：DP[v]=max(DP[v],DP[v−i.weight]+i.value)DP[v]=max(DP[v],DP[v-i.weight]+i.value)DP[v]=max(DP[v],DP[v−i.weight]+i.value) 注：DP[v]DP[v]DP[v]为不放时所获的值 DP[v−i.weight]+i.valueDP[v-i.weight]+i.valueDP[v−i.weight]+i.value为放时所获的值 If you have QuestionIf\ you\ have\ QuestionIf you have Question为什么使用逆推不用顺推？？？ 初学的本蒟蒻在一开始整理个人笔记时也有该问题... 但是如果你通过YBT原题给出样例去填表发现 很明显顺推情况下DP表是错误的 因为在顺推情况下DP[v]DP[v]DP[v]会存到同一轮前面的值也就是相当于存了DP[i][v−i.weight]DP[i][v-i.weight]DP[i][v−i.weight]但我们要的是DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight] 这样在优化后01背包的空间复杂度为O(M)O(M)O(M)了 优化代码：

不会还有人不知道什么是reverse吧QAQ

无

Day09 树图 👉：https://www.acgo.cn/discuss/study/24864

#include <iostream> using namespace std; int main() { int k,n=1,s=0; cin>>k; while(k-n>=0) { s+=nn; k-=n; n++; } s+=kn; cout<<s; }

快去做😂👍

你不会还在用: 那可就太LOW了，像我这样，用这个:

再见，上海营 --2024.08.09 19:38--

Day06-深度优先搜索 供复习练习题 1. 逃离迷宫 2. 全排列 3. 全序列 应用： 1. 细胞 2. 选数 Day07-广度优先搜索 供复习练习题： 1. 一石激起千层浪 2. 红与黑 练习： 1. 神庙3 2. 时空穿梭 3. 太平洋水流 Day08👉: https://www.acgo.cn/discuss/study/24736

#include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; cout<<"1"; return 0; }

在此题中若根据题干输出"I’m lucky.“会导致WA。 WA代码： 此处的"I’m lucky.“从题干复制，引号为中文符号，提交结果为： 而若将其中的引号改为英文符号 代码： 提交结果为： 具体可见：

简单， long一下， 比一下。

为什么老师也算学生啊？而且老师是最高的吗？（QAQ）

6

#include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <vector> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 5; typedef long long LL; struct node{ long long next; bool a, b, c; }; long long n, ans; int dir[3] = {3, 5, 7}; void dfs(long long x, bool f3, bool f5, bool f7){ if(x > n) return ; if(f3 && f5 && f7) ans++; dfs(x * 10 + 3, 1, f5, f7); dfs(x * 10 + 5, f3, 1, f7); dfs(x * 10 + 7, f3, f5, 1); } void bfs(int x){ queue<node> q; q.push({0, 0, 0, 0}); while(q.size()){ node now = q.front(); q.pop(); if(now.a && now.b && now.c){ ans++; } node p = now; p.next = now.next * 10 + 3; p.a = 1; if(p.next <= n) q.push(p); p = now; p.next = now.next * 10 + 5; p.b = 1; if(p.next <= n) q.push(p); p = now; p.next = now.next * 10 + 7; p.c = 1; if(p.next <= n) q.push(p); } } int vis[5]; bool init(long long x){ if(x > n) return 0; if(vis[0] && vis[1] && vis[2]) return 1; return 0; } void solve(){ for(int i = 0; i < 3; i++){ vis[i]; for(int j = 0; j < 3; j){ vis[j]; for(int k = 0; k < 3; k){ vis[k]; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100); for(int p = 0; p < 3; p){ vis[p]; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000); for(int l = 0; l < 3; l){ vis[l]; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000); for(int m = 0; m < 3; m){ vis[m]; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000); for(int q = 0; q < 3; q){ vis[q]; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000 + dir[q] * 1000000); for(int h = 0; h < 3; h){ vis[h]; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000 + dir[q] * 1000000 + dir[h] * 10000000); for(int v = 0; v < 3; v){ vis[v]++; ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000 + dir[q] * 1000000 + dir[h] * 10000000 + dir[v] * 100000000); vis[v]--; } vis[h]--; } vis[q]--; } vis[m]--; } vis[l]--; } vis[p]--; } vis[k]--; } vis[j]--; } vis[i]--; } } int main(){ //freopen("number.in", "r", stdin); //freopen("number.out", "w", stdout); cin >> n; // dfs(0, 0, 0, 0); // bfs(0); solve(); cout << ans; }