智能建站实验报告,成功营销网站,甘肃省省建设厅网站,x wordpress theme文章目录 前言一、完全背包的状态设计1、状态设计2、状态转移方程3、对比0/1背包问题4、时间复杂度分析 二、完全背包问题的优化1、时间复杂度优化2、空间复杂度优化 三、OJ练习裸题完全背包离散化最小值 前言 完全背包问题#xff0c;相比0/1背包问题#xff0c;实就每个物品… 文章目录 前言一、完全背包的状态设计1、状态设计2、状态转移方程3、对比0/1背包问题4、时间复杂度分析 二、完全背包问题的优化1、时间复杂度优化2、空间复杂度优化 三、OJ练习裸题完全背包离散化最小值 前言 完全背包问题相比0/1背包问题实就每个物品可以取无限次。 一、完全背包的状态设计 有n(n≤100)种物品和一个容量为m(m≤10000)的背包。第i种物品的容量是c[i]价值是w[i]。现在需要选择一些物品放入包 每种物品可以无限选择,组总容量不能超过背包容量求能够达到的物品的最大总价值。 以上就是完全背包问题的完整描述和0/1背包的区别就是每种物品可以无限选取;
1、状态设计
状态(i , j)表示前 i 种物品恰好放入容量为 j 的背包(0 ≤ i n, 0 ≤ j ≤ m)令 dp[i][j]示状态(i, j)下该背包得到的最大价值即前 i 种物品(每种物品可以选择无限件)恰好放入容量为j的背包所得到的最大总价值;
2、状态转移方程 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j − c [ i ] ∗ k ] w [ i ] ∗ k ) ( 0 ≤ k ≤ j / c [ i ] ) dp[i][j] max(dp[i- 1][j -c[i]*k] w[i] *k) (0≤k≤j/c[i]) dp[i][j]max(dp[i−1][j−c[i]∗k]w[i]∗k)(0≤k≤j/c[i])
因为每种物品有无限种可放置将它归类为以 下两种情况:
不放如果“第 i 种物品不放入容量为 j 的背包那么问题转化成求** 前i - 1种物品放入容量为 j 的背包的问题所以最大价值就等于前i - 1种物品放入容量为 j 的背包的最大价值**对应状态转移方程中k 0的情况即dp[i-1][j]放k个如果第 i 种物品放入容为j的背包,那么问题转化成求前 i - 1 种物品放入容量为j - c[i] * k的背包的问题那么此时最大价值就等于前i - 1种物品放入容量为j-c[i] * k的背包的最大价值加上放入 k 个第 i 种物品的价值即dp[i-1][j - c[i] * k] w[i] * k 枚举所有满足条件的 k 就是我们所求的 “前i种物品恰好放入容为j的背包” 的最大价值了。 注意由于每件物品都可以无限选择所以这里描述的时候都是用的种作为单位即代表不同种类的物品。
3、对比0/1背包问题
完全背包问题是0/1包问题的扩展区别就是它可以选择取0件、取1件、取2 件、取…k件而0/1包问题只能取0件、取1件。如果从状态转移方程出发,我们可以把两个问题进行归纳统一得到一个统一的状态转移方程如下: d p [ i ] [ j ] m a x ( d p l i − 1 ] [ j − c [ i ] ∗ k ] w [ i ] ∗ k ) dp[i][j] max(dpli- 1][j-c[i]*k] w[i]*k) dp[i][j]max(dpli−1][j−c[i]∗k]w[i]∗k)
对于0/1包问题k的取值为0, 1对于完全背包问题k的取值为0, 1, 2, 3, ……, j / c[i];
4、时间复杂度分析
对于n种物品放入一个容量为m的背包状态数为O(nm)每次状态转移的消耗为O(k)所以整个状态转移的过程时间复杂渡是大于O(nm)的那么实际是多少呢? 考虑最坏情况下即c[i] 1时那么要计算的dp[][j]的转移数为 nm **总的状态转移次数就是nm2**所以整个算法的时间复杂度是O(nm2)的也就是说状态转移均摊时间复杂度是O(m)的。 接下来一节会对完全背包问题的时间和空间复杂度进行优化。
二、完全背包问题的优化
1、时间复杂度优化
我们把状态转移方程进行展开后得到如下的k1个式子: d p [ i ] [ j ] m a x { d p [ i − 1 ] [ j ] ( 1 ) d p [ i − 1 ] [ j − c [ i ] ] w [ i ] ( 2 ) d p [ i − 1 ] [ j − c [ i ] ∗ 2 ] w [ i ] ∗ 2 ( 3 ) . . . d p [ i − 1 ] [ j − c [ i ] ∗ k ] w [ i ] ∗ k ( k 1 ) dp[i][j]\,max\left\{\begin{align} dp[i-1][j](1)\\ dp[i-1][j-c[i]]w[i](2)\\ dp[i-1][j-c[i]*2]w[i]*2(3)\\ ...\\ dp[i-1][j-c[i]*k]w[i]*k(k1)\\ \end{align}\right. dp[i][j]max⎩ ⎨ ⎧dp[i−1][j]dp[i−1][j−c[i]]w[i]dp[i−1][j−c[i]∗2]w[i]∗2...dp[i−1][j−c[i]∗k]w[i]∗k(1)(2)(3)(k1) 利用待定系数法用j - c[i]代替上式的 j 得到如下式子: d p [ i ] [ j − c [ i ] ] m a x { d p [ i − 1 ] [ j − c [ i ] ] ( 1 ) d p [ i − 1 ] [ j − c [ i ] ∗ 2 ] w [ i ] ( 2 ) d p [ i − 1 ] [ j − c [ i ] ∗ 3 ] w [ i ] ∗ 2 ( 3 ) . . . d p [ i − 1 ] [ j − c [ i ] ∗ k ] w [ i ] ∗ ( k − 1 ) ( k ) dp[i][j-c[i]]\,max\left\{\begin{align} dp[i-1][j-c[i]](1)\\ dp[i-1][j-c[i]*2]w[i](2)\\ dp[i-1][j-c[i]*3]w[i]*2(3)\\ ...\\ dp[i-1][j-c[i]*k]w[i]*(k-1)(k)\\ \end{align}\right. dp[i][j−c[i]]max⎩ ⎨ ⎧dp[i−1][j−c[i]]dp[i−1][j−c[i]∗2]w[i]dp[i−1][j−c[i]∗3]w[i]∗2...dp[i−1][j−c[i]∗k]w[i]∗(k−1)(1)(2)(3)(k) 等式两边都加上w[]得到: d p [ i ] [ j − c [ i ] ] w [ i ] m a x { d p [ i − 1 ] [ j − c [ i ] ] w [ i ] ( 1 ) d p [ i − 1 ] [ j − c [ i ] ∗ 2 ] w [ i ] ∗ 2 ( 2 ) d p [ i − 1 ] [ j − c [ i ] ∗ 3 ] w [ i ] ∗ 3 ( 3 ) . . . d p [ i − 1 ] [ j − c [ i ] ∗ k ] w [ i ] ∗ k ( k ) dp[i][j-c[i]]w[i] \, max \left\{\begin{align} dp[i-1][j-c[i]]w[i](1)\\ dp[i-1][j-c[i]*2]w[i]*2(2)\\ dp[i-1][j-c[i]*3]w[i]*3(3)\\ ...\\ dp[i-1][j-c[i]*k]w[i]*k(k)\\ \end{align}\right. dp[i][j−c[i]]w[i]max⎩ ⎨ ⎧dp[i−1][j−c[i]]w[i]dp[i−1][j−c[i]∗2]w[i]∗2dp[i−1][j−c[i]∗3]w[i]∗3...dp[i−1][j−c[i]∗k]w[i]∗k(1)(2)(3)(k) 于是我们发现这里的(1…k)式等价于最开始的状态转移方程中的(2) … (k1)式所以原状态转移方程可以简化为: d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − c [ i ] ] w [ i ] ) dp[i][j]\,max(dp[i-1][j],dp[i][j-c[i]]w[i]) dp[i][j]max(dp[i−1][j],dp[i][j−c[i]]w[i])
这样就把原本均摊时间复杂度为O(m)的状态转移优化到了O(1)。 那么我们来理解一下这个状态转移方程的含义: 对于第i种物品其实只有两种选择: 一个都不放、至少放一个。 一个都不放就是前i - 1种物品放满一个容量为 j 的背包的情况即dp[i-1][i] 至少放一个的话我们在”前i种物品装满j - c[i]容量的背包“的情况中再塞一个第i种物品就能保证至少放一个第i种物品了此时的价值为dp[i][j - c[i]] w[i]最大价值即二者取大。
如果只是为了掌握完全背包的模板那么这个公式可以开头就讲但是许多动态规划问题都不是裸题需要我们从问题本身入手一步步的分析优化从而解决问题所以了解原理及公式推导是很有必要的。
2、空间复杂度优化
空间复杂度优化不用说就能猜到一定又是滚动数组优化因为状态转移方程提示的已经很明显了我们仍然从状态图上来观察是否可以进行滚动数组优化。
根据优化后的状态转移方程我们发现状态转移的过程如图所示: 蓝色的格子代表的是已经计算出来的状态红色的格子代表的是当前正在计算的状态即dp[i][j]它的值来自dp[i-1][j]和dp[i][j-c[i]]这两个值对应的格子一定是蓝色的绿色色的格子代表尚未进行计算的状态;
为了将问题描述的更加清晰我们把(i, j)看成是二维笛卡尔坐标系上的点i在x轴上, j在y轴上如图所示: 任何一个状态在计算出来以后只会给x坐标比它大或者y坐标比它大的使用所以我们只需要保留一行状态按照x递增进行顺序计算,就可以做到把二维的问题转换成一维,将状态转移方程变成如下表示: d p [ j ] m a x ( d p [ j ] , d p [ j − c [ i ] ] w [ i ] ) dp[j]\,max(dp[j],dp[j-c[i]]w[i]) dp[j]max(dp[j],dp[j−c[i]]w[i])
三、OJ练习
裸题
P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
友情提示不开long long见祖宗
很直白的裸题t就是背包容量给了m种物品求最大价值。
直接跑板子最后一个点不开long long会错
AC代码如下
#include iostream
#include cstring
using namespace std;
#define N 10010
#define M 10000010
#define int long long
int t, m;
int c[N], w[N], dp[M]{0};signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);cin t m;for (int i 0; i m; i)cin c[i] w[i];for (int i 0; i m; i)for (int j c[i]; j t; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[t];return 0;
}
[P2722 USACO3.1] 总分 Score Inflation - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
同样裸题直接跑板子即可。
AC代码如下
#include iostream
#include cstring
using namespace std;
#define N 10010
#define M 10010
#define int long long
int t, m;
int c[N], w[N], dp[M]{0};signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);cin t m;for (int i 0; i m; i)cin w[i] c[i];for (int i 0; i m; i)for (int j c[i]; j t; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[t];return 0;
} 完全背包离散化
P1853 投资的最大效益 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
根据题目呢如果我们不考虑n年后的情况只考虑第一年能够得到的最大资产那么很简单就是一个完全背包问题的裸题我们把债券当作物品初始总资产当作容量求出最大收益然后最大收益加上初始总资产就是第一年能够得到的最大资产
那么n年的情况呢
我们发现他这个债券机制太科幻了我们每年得到收益后还能原价卖出债券下一年再拿新的资产去选择新的债券购买方案虽然不知道现实中有没有这种好事但是对于我们做题而言反而简单了。
我们第一年结束得到了新的资产第二年拿着第一年的资产再来一次完全背包年底再卖掉第三年拿着第二年的资产再来……
我们发现所谓的n年就是让你跑n次完全背包罢了
到这里可以直接写板子了加一层循环罢了。但是你的资产越来越大也就是说你的状态数组dp的空间就有要求了很可能再某一年你的背包直接爆炸了
我们发现题目里说了债券的价格为1000的倍数那么我们就可以将数据离散化了
状态转移过程中把容量除以1000物品体积也除以1000价值不做改变这样我们原先最大价值为dp[s]这样一来就变成了dp[s/1000]了就有了下面的代码
AC代码如下
#include iostream
#include cstring
using namespace std;
#define N 10010
#define M 1000010
#define int long long
int s, n, d;
int c[N], w[N], dp[M]{0};signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);cin s n d;for (int i 0; i d; i){cin c[i] w[i];}for (int k 0; k n; k){memset(dp, 0, sizeof(dp));for (int i 0; i d; i)for (int j c[i] / 1000; j s / 1000; j)dp[j] max(dp[j], dp[j - c[i] / 1000] w[i]);s dp[s / 1000];}cout s;return 0;
}
最小值
[P2918 USACO08NOV] Buying Hay S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
不难想到这是个完全背包的问题那么对问题进行抽象怎样选取物品和容量呢这里给出两种角度两种角度有着不同的处理细节。
F1 每个公司package的重量为价值价格为体积
这样思考其实是很简单粗暴也是最好理解的我们即然要求购买干草量不小于目标值的所有方案中的最小花费那么我们设定一个总花费的上限然后以上限为总容量以每个公司的包裹为n种物品其重量为价值价格为体积
这样我们跑一遍完全背包后只要找到满足dp[j] s的最小j即可s为需要购买的干草重量
显然dp[j]是单调递增的钱越多买的越多嘛所以直接二分查找答案并输出即可。
#include iostream
#include cstring
using namespace std;
#define N 110
#define M 100000
#define int long long
int s, n, ans M;
int c[N], w[N], dp[M 1]{0};signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);freopen(in.txt, r, stdin);freopen(out.txt, w, stdout);cin n s;for (int i 0; i n; i)cin w[i] c[i];for (int i 0; i n; i)for (int j c[i]; j M; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout (lower_bound(dp[0], dp[M], s) - dp[0]);return 0;
}
F2 每个公司package的价格为价值重量为体积
这样的话先不考虑具体代码的实现最终我们的答案就是dp[s]了吗
不一定很可能实际情况情况导致我们不能恰购买s的干草即物品的体积导致容量s背包装不满此时dp[s]为非法值所以我们最终要找到一个dp[j]最小的jjs
这样的话我们由于求的是最小花费所以这里状态转移的时候要转移最小值所以不可避免地要对dp数组预处理为很大的非法值。
初态dp[0] 0背包容量的上限为s 5000这个根据数据范围很好得出
直接上代码
#include iostream
#include cstring
#include algorithm
using namespace std;
#define N 110
#define M 55010
#define int long long
int s, n, ans M;
int c[N], w[N], dp[M]{0};signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);//freopen(in.txt, r, stdin);//freopen(out.txt, w, stdout);cin n s;for (int i 0; i n; i)cin c[i] w[i];memset(dp, 0x3f, sizeof(dp));dp[0] 0;for (int i 0; i n; i)for (int j c[i]; j s 5000; j)dp[j] min(dp[j], dp[j - c[i]] w[i]);cout *min_element(dp[s], dp[s 5001]);return 0;
}
