01背包01背包（0-1KnapsackProblem）有NNN件物品和一个容量为VVV的背包。放入第iii件物品耗费的费用是CiC_iCi,得到的价值为WiW_iWi。求解将哪些物品装入背包可以使价值总和最大设F[i,v]F\left[i,v\right]F[i,v]表示前iii件物品敲好放入一个容量为vvv的背包可以获得的最大价值，容易写出F[i,v]=max{F[i−1,v],F[i−1,v−Ci]+Wi}F\left[i,v\right]=\max\left\{F\left[i-1,v\right],F\left[i-1,v-C_i\right]+W_i\right\}F[i,v
01背包01背包（0-1KnapsackProblem）有NNN件物品和一个容量为VVV的背包。放入第iii件物品耗费的费用是CiC_iCi,得到的价值为WiW_iWi。求解将哪些物品装入背包可以使价值总和最大设F[i,v]F\left[i,v\right]F[i,v]表示前iii件物品敲好放入一个容量为vvv的背包可以获得的最大价值，容易写出F[i,v]=max{F[i−1,v],F[i−1,v−Ci]+Wi}F\left[i,v\right]=\max\left\{F\left[i-1,v\right],F\left[i-1,v-C_i\right]+W_i\right\}F[i,v
背包1.创建背包面板Grid用GridLayoutGroup组件布局，子物体会在Grid里面成网格布局2.创建数据库Bag.csBag数据库，保存背包所有的item[CreateAssetMenu(menuName="Bag/NewBag")]publicclassBag:ScriptableObject{publicListItem>ItemList=newListItem>();}//CreateAssetMenu可创建一个资源菜单，来新建这个ScriptableObjectItem.csItem数据库字段[CreateAssetMenu(menuName="Bag/NewItem")]p
背包1.创建背包面板Grid用GridLayoutGroup组件布局，子物体会在Grid里面成网格布局2.创建数据库Bag.csBag数据库，保存背包所有的item[CreateAssetMenu(menuName="Bag/NewBag")]publicclassBag:ScriptableObject{publicListItem>ItemList=newListItem>();}//CreateAssetMenu可创建一个资源菜单，来新建这个ScriptableObjectItem.csItem数据库字段[CreateAssetMenu(menuName="Bag/NewItem")]p
题目描述：解题思路：整体思路：利用动态规划，其目的就是将原问题分解成几个子问题，通过求解简单的子问题，把原问题给解决，就比如斐波那契数列方程：f[i]=f[i-1]+f[i-2];动态规划的核心就是找到原问题与子问题的关系，并列出动态转移方程。实现方法：这里我们可以定义一个二维数组，dp[i][j]表示对于背包容量为j的背包，前i个物品的最优解，即最大价值。对于一个物品，可以分两种情况：不选：对于dp[i][j]，不选第i个物品时，dp[i][j]的最优解就是dp[i-1][j]的最优解选：如果选择，我们就让背包容量减去第i件的物品体积，让dp加上物品价值，即dp[i][j]=dp[i-1][
目录一、0-1背包1.1、0-1背包解决的问题1.2、dp数组定义1.3、转移方程1.3.1、二维dp数组1.3.2、一维dp数组1.4、遍历顺序1.5、测试代码1.6、练习二、完全背包2.1、完全背包解决问题2.2、与0-1背包的区别2.3、测试代码2.4、拓展问题：装满背包有几种方法？2.5、排列与组合2.5.1、组合2.5.2、排列2.6、练习一、0-1背包1.1、0-1背包解决的问题 给你i个物品，每个物品都具有两个属性（价值value[i]和重量weight[i ]），将他们放入容量为j的背包中（不可以重复放入同一个物品），怎么放才能让背包的价值最大？1.2、dp数组定义一维和
分支限界法的基本思想分支限界法的基本思想是，在分支结点上，预先分别估算沿着它的各个儿子结点向下搜索的路径中，目标函数可能取得的“界”，然后把这些儿子结点和它们可能所取得的“界”保存在一张结点表中，再根据题目要求选择表中“界”最大或最小的结点向下搜索。（一般用优先队列来处理这张结点表）这样当搜索到一个叶子结点时，如果该结点所估算的目标函数值就是结点表中的最大或者最小值，那么沿叶子结点到根结点的路径所确定的解就是问题的最优解，叶子结点的目标函数值就是问题的最大值或最小值。参考：《算法分析与设计（第三版）》（郑宗汉、郑晓明编著）解决背包问题的基本思路首先要将物品按重量价值比排序。同样还是一棵二叉树，
使用分支限界法求解01背包问题，3个物品，重量和价值，背包容量（1）画出解空间树（2）Say如何剪枝（3）求出最优解假设物品的个数n=3，背包容量W=30，重量w=（16,15,15），价值v=（45,25,25）（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。（1）画出解空间树迷惑点：解空间树书上给的是一个排列树，把超重的情况也画出来了，其实是无用功，那么如果考虑超重的话，就在D的时候就已经超重了，就不需要画出来，但是书上却把它称之为搜索空间树，所以我们画
补充：对于01背包而言，二维dp数组两层for循环正向遍历，可以交换遍历顺序；但是对于一维dp数组来说，两层for循环不能交换顺序，只能先遍历物品再遍历背包且背包要倒叙遍历。对于完全背包来说，两层for循环可以交换遍历顺序，但是有区别的，都是正向遍历，但是如果先遍历背包后遍历物品就是排列数，先遍历物品再遍历背包就是组合数。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。01背包的问题描述：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪
给定n种物品和一背包。物品i的重量是wiw_iwi，其价值为viv_ivi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?对于一种物品，要么装入背包，要么不装。解法一：暴力递归可能性分析：f(i,rest)物品i，背包容量为rest时，能装入的物品的最大总价值。物品i放入背包：res1=f(i+1,rest-w[i])物品i不放入背包：res2=f(i+1,rest)决策：res=max(res1,res2)算法模型：从左向右依次对每个元素进行尝试（保留或者丢弃），根据最大值决策。01背包问题，可能性尝试题里已经明确说明了（放入背包或者丢弃），也有很多其他题，
