dede 网站模板,python做网站部署,建设购物网站要求,用易语言做刷网站注册软件前言
什么是背包问题#xff1f;
背包问题是一种经典的组合优化问题#xff0c;它的核心思想是在有限的资源#xff08;如背包的容量#xff09;下#xff0c;如何选择物品以达到某种目标#xff08;如最大价值#xff09;的最优解。
背包问题可以分为几种类型#…前言
什么是背包问题
背包问题是一种经典的组合优化问题它的核心思想是在有限的资源如背包的容量下如何选择物品以达到某种目标如最大价值的最优解。
背包问题可以分为几种类型其中最常见的有
0/1背包问题每个物品只能选择放入或不放入背包不能分割。完全背包问题每种物品可以选择无限个但每件物品只能选择一次。多重背包问题每种物品可以选择多个且没有数量限制。
解决方法也有很多比如动态规划回溯搜索、分支限界贪心等。
背包问题在实际生活中有很多应用如资源分配、项目投资组合、货物装载、课程安排等。通过解决背包问题我们可以在有限的资源下做出最优的决策。
本节我们就来看01背包问题。
问题描述
01背包问题的描述如下
现在我们有一个背包它有一个固定的承载重量限制 W背包容量有限。同时我们有一组物品每个物品都有自己的重量weight[i]和价值value[i]。我们需要从这组物品中选择一些物品放入背包并且每件物品只能用一次问在不超过背包承载重量的前提下放入背包的物品总价值最大是多少 在01背包中每个物品最多只能用一次。 问题求解
暴力
在这个经典的 01背包问题中对于我们的决策每一件物品只有两个状态
选不选
使用回溯法我们可以搜索出所有情况但时间复杂度是 O ( 2 n ) O(2^n) O(2n) n n n表示物品数量因此暴力的解法是通不过的需要进一步优化。
对于01背包问题最常用的求解方法是动态规划。
dp表的含义
使用动态规划的解法需要定义状态明确dp表的含义和状态转移方程将问题分解为子问题然后通过迭代的方式从小问题开始逐步解决大问题。
我们来看在01背包问题中状态是如何定义的
dp[i][j]在前i个物品中选取若干个使得总重量不超过j的情况下能够获得的最大价值。
明确好dp表的含义后我们就可以进行状态转移的讨论以及编码。
状态转移
对于每个物品i以及当前的背包容量j我们考虑两种情况选或不选
如果不选取第i个物品 那么背包中物品的总价值就是在前i-1个物品中选取若干个使得总重量不超过j的情况下能够获得的最大价值即dp[i][j] dp[i - 1][j]。 如果选取第i个物品 背包中物品的总价值就是在前i-1个物品中选取若干个使得总重量不超过j-weight[i]的情况下能够获得的最大价值再加上第i个物品的价值即dp[i][j] dp[i - 1][j - weight[i]] value[i]。
我们对每个物品的每种可能性进行考虑从而找出在总重量不超过背包容量的前提下能够获得的最大价值。这就是01背包问题的解题思路。
解题流程
定义好状态以及转移方程后我们就可以开始推了。从第1个物品开始对于每个物品遍历所有的背包容量根据状态转移方程更新dp表。最后dp[n][t]就是最大价值。 在使用动态规划时初始化操作是很关键的一步。对于dp[0][j]没有物品时无论背包容量是多少最大价值都是0因此初始化就都是0。 代码如下
/*** 使用动态规划解决01背包问题* param weight 物品的重量数组* param value 物品的价值数组* param W 背包的总容量* return 能够获得的最大价值*/
public static int compute(int[] weight, int[] value, int W) {int n value.length; // 有n件物品// dp[i][j]表示在前i个物品中选取若干个使得总重量不超过j的情况下能够获得的最大价值int[][] dp new int[n1][W1];// 遍历每一个物品for(int i 1; in; i) {// 遍历每一种背包容量for(int j 0; jW; j) {// 不选取第i个物品dp[i][j] dp[i-1][j];// 如果背包的剩余容量大于等于当前物品的重量考虑选取第i个物品if(j weight[i]) {// 选取第i个物品更新最大价值dp[i][j] Math.max(dp[i][j], dp[i-1][j-weight[i]] value[i]);}}}// 返回在前n个物品中选取若干个使得总重量不超过W的情况下能够获得的最大价值return dp[n][W];
}空间压缩
在上述代码中我们可以看到每次更新dp[i][j]时我们只用到了上一行的数据即dp[i-1][j]和dp[i-1][j-weight[i]]。这意味着我们并不需要保存所有的dp[i][j]只需要保存上一行的数据就足够了因此我们可以将二维dp表改进为一维俗称空间压缩。
空间压缩的思路是我们使用一个一维数组dp[j]来代替二维数组dp[i][j]。dp[j]表示在当前考虑的物品中选取若干个使得总重量不超过j的情况下能够获得的最大价值。
需要注意的是我们每次在更新dp[i][j]时总是用到了上一行中的dp[i-1][j]和dp[i-1][j-weight[i]]在二维表中可以形象理解为我所处的位置依赖于上方的格子以及左上方的格子。因此进行空间压缩更新dp[j]时我们需要从后往前更新dp[j]这样可以逐渐更新当前的格子。 如果我们从前往后更新那么在计算dp[j]时dp[j-weights[i]]可能已经被更新过了它表示的是当前行的状态而不是上一行的状态。而我们需要的是上一行的状态因此我们必须从后往前更新。 下面是空间压缩后的代码
/*** 使用动态规划解决01背包问题空间压缩版本* param weight 物品的重量数组* param value 物品的价值数组* param W 背包的总容量* return 能够获得的最大价值*/
public static int compute(int[] weight, int[] value, int W) {int n value.length; // 有n件物品// dp[j]表示在当前考虑的物品中选取若干个使得总重量不超过j的情况下能够获得的最大价值int[] dp new int[W1];// 遍历每一个物品for(int i 1; in; i) {// 从后往前更新dp[j]for(int j W; jweight[i]; j--) {// 选取第i个物品更新最大价值dp[j] Math.max(dp[j], dp[j-weight[i]] value[i]);}}// 返回在所有物品中选取若干个使得总重量不超过W的情况下能够获得的最大价值return dp[W];
}这段代码的时间复杂度仍然是 O ( n ∗ W ) O(n*W) O(n∗W)但是空间复杂度降低到了 O ( W ) O(W) O(W)其中 n n n是物品的数量 W W W是背包的容量。
注意我们后面会经常使用空间压缩的版本因此需要吃透这份代码。
模板题 | 采药
我们来看一道洛谷上的模板题。 测试链接P1048 [NOIP2005 普及组] 采药 题目描述
辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”
如果你是辰辰你能完成这个任务吗
输入格式
第一行有 2 2 2 个整数 T T T 1 ≤ T ≤ 1000 1 \le T \le 1000 1≤T≤1000和 M M M 1 ≤ M ≤ 100 1 \le M \le 100 1≤M≤100用一个空格隔开 T T T 代表总共能够用来采药的时间 M M M 代表山洞里的草药的数目。
接下来的 M M M 行每行包括两个在 1 1 1 到 100 100 100 之间包括 1 1 1 和 100 100 100的整数分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例
样例输入
70 3
71 100
69 1
1 2样例输出
3提示
【数据范围】
对于 30 % 30\% 30% 的数据 M ≤ 10 M \le 10 M≤10对于全部的数据 M ≤ 100 M \le 100 M≤100。
【题目来源】
NOIP 2005 普及组第三题
解题
这道题就是标准的01背包问题每种草药只能采摘一次也就是说每种物品只能选择一次或者不选择不能选择多次。
我们定义dp[i][j]为在前i种草药中选取若干种使得总时间不超过j的情况下能够获得的最大价值。对于第i种草药我们可以选择采摘也可以选择不采摘。如果我们选择采摘那么我们需要在剩余的时间j-weight[i]中选择前i-1种草药使得总价值最大如果我们选择不采摘那么我们需要在时间j中选择前i-1种草药使得总价值最大。
我们取这两种情况的最大值就是dp[i][j]的值。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static int N 101; // 草药的最大数量static int W 1001;// 总时间的最大值static int[] weight new int[N]; // 每种草药的采摘时间static int[] value new int[N]; // 每种草药的采摘价值static int n, w; // 分别表示草药的数量和总时间public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in new StreamTokenizer(br);PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() ! StreamTokenizer.TT_EOF) {w (int) in.nval;in.nextToken();n (int) in.nval;for (int i 1; i n; i) {in.nextToken();weight[i] (int) in.nval;in.nextToken();value[i] (int) in.nval;}out.println(compute2());}out.flush();out.close();br.close();}// 经典解法public static int compute1() {// dp[i][j]表示在前i个草药中选取若干个使得总时间不超过j的情况下能够获得的最大价值int[][] dp new int[n 1][w 1];for (int i 1; i n; i) {for (int j 0; j w; j) {// 不要i号草药dp[i][j] dp[i - 1][j];if (j - weight[i] 0) {// 要i号草药dp[i][j] Math.max(dp[i][j], dp[i - 1][j - weight[i]] value[i]);}}}return dp[n][w];}// 空间压缩版本public static int compute2() { int[] dp new int[w 1];for (int i 1; i n; i) {for (int j w; j weight[i]; j--) {dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}return dp[w];}}力扣题单
链接题解2915. 和为目标值的最长子序列的长度题解416. 分割等和子集题解494. 目标和题解2787. 将一个数字表示成幂的和的方案数题解1049. 最后一块石头的重量 II题解
