java题目求解

来源：蜘蛛抓取(WebSpider) 时间：2022-06-07 03:07 标签： java程序分析题

   这是最基础的背包问题，特色是：每种物品仅有一件，能够选择放或不放。函数

面对每一个物品，咱们只有选择拿与不拿两种选择，不可以选择装入物品的一部分，也不能装入同一物品屡次。spa

2)   当 v >= W[i] 时，这是背包容量能够放下第i件物品，能够选择拿仍是不拿，判断标准：拿这件物品是否能获取更大的价值。for循环

究竟拿不拿，取决于哪一种状况使价值最大，由此可获得状态转移方程： 

//若是容量为j的背包放得下第i个物体
 //两种选择：放与不放第i个物体，策略：哪一个使价值最大就选用哪一种策略
 //放不下，只能选择不放第i个物体
 

 咱们最终要求的就是： F[ N ] [ V ]，表示 N件物品恰放入一个容量恰为V的背包能够得到的最大价值。
 
 

 举例分析：假设有5个物体，背包容量为10，物体的体积分别是2 2 6 5 4，物体的收益分别是6 3 5 4 6。假设要求F[1][3]，则须要求解的是：
 
 

 
 

 
 

 
 
 

 
 

 其时间复杂度已经不能再优化了，可是空间复杂度能够优化到O(V)，具体看2.4节。

2.3 如何肯定哪些物品构成最大价值？ 

 

 在3.1节咱们已经能够肯定每一种状态可得到的最大价值，可是并不清楚具体选择哪几样物品可以得到最大价值。
 
 

 那么，如何肯定哪几样物品可以得到最大价值呢？
 
 

 
 

 F[i][j]，它是最优值，那么若是：
 
 
 

 具体实现代码能够看3.2节。

2.4 空间复杂度优化（降维） 

 

 空间复杂度能够优化为O(V)，只适用于求最大价值，可是若是要求解哪些物体构成最大价值，则不能够降维。
 
 

 
 

 

 

 考虑3.1节基本思路的具体实现，每一次都有一个主循环i = 1 .. N，每次算出来二维数组F[ i ][0 .. V]的全部值。那么，若是只用一维数组F[0 .. V]，能不能保证 第i次循环结束后F[v]中表示的就是咱们定义的状态F[i][v]呢？

 

 
 

 
 

 看上面的伪代码，其实对于外层循环的每个i值，实际上是不须要记录的。在进行第i次循环时，全部的F[0 ... V]都还未更新时，F[v]此时记录的表示前i-1个物品在背包空间为 v 时的最大价值，这样就至关于还记录着F[i-1,v]和F[i-1,v-Ci]。
 
 

 那么为什么内层循环要递减遍历？
 
 

 第i次循环时，刚开始F[0 ... V]还未更新时，F[v]此时记录的表示前i-1个物品在背包空间为 v 时的最大价值，那么如何保证F[v]在进行更新时，每一次用到的最优值都是未更新前的？ 进行逆序遍历，就能够保证更新正确。
 
 

 2000，此时max用到的F[2]是已经更新过的，因此正序遍历会形成错误的结果。
 
 

 那么为何逆序遍历就不会出错了呢？
 
 

 
 

 
 

 虽然降维有效下降了空间复杂度，可是若是题目要求算出哪些物体组成最大价值的话，仍是得用二维数组。具体可看2.3节。
 
 

 java具体实现代码在3.3小节。

2.5 扩展——改为“刚好装满背包” 

 

 求最优解的背包问题中，有两种不太相同的问法：
  • 有的题目要求“刚好装满背包”时的最优解
  • 有的题目则没有要求必须把背包装满 
 

 一种实现方法的区别仅在初始化的时候有所不一样：
  • 对于第一种问法，要求刚好装满背包，那么在初始化时除了F[0]为0，其他F[1 .. V]均设为-INF，这样就能够确保最终获得的F[V]是一种刚好装满背包的最优解。
  • 若是没有要求必须把背包装满，只是但愿价格尽可能大，初始化时应该将F[0 .. V]所有设为0。
  • 初始化的F数组事实上就是在没有任何物体放进背包的合法状态。若是要求背包刚好装满，那么此时只有容量为0的背包能够在什么也不装且价值为0的状况下被“刚好装满”，其它容量的背包均没有合法解，属于未定义的状态，应该赋值为-INF。
  • 若是背包并不是必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，因此初始时状态的值所有为0。 
 

 为何取负无穷大为不合法的状态？
 
 

 由于状态选择方程中，F[v]是经过max函数取值较大的那个，因此将不合法的状态设为负无穷，则这种状态怎么样都不会被选到。
 
 

 
 

 
 

 
 

 
 
 * 使用二维数组非递归的方法求解0/1背包问题
 // N表示物体的个数，V表示背包的载重
 //用于存储每一个物体的重量，下标从1开始
 //存储每一个物体的收益，下标从1开始
 //二维数组，用来保存每种状态下的最大收益
 //对二维数组F进行初始化
 //注意边界问题，i是从1开始的，j是从0开始的
 //若是容量为j的背包放得下第i个物体
 //放不下，只能选择不放第i个物体
 //打印全部结果，咱们要求的是F[N][V]
 * 求解F[n][m]这个最优值具体选取哪几样物品能得到最大价值，但只会输出一种状况
 * 第一行是物体个数、背包总空间；
 * 第二行是每一个物体的空间；
 * 第三行是每一个物体的收益。
 //下标从1开始，表示第1个物品
 3.2 肯定哪些物品构成最大值
 
 

 在3.1的代码基础上添加如下代码：
 
 * 求解F[n][m]这个最优值具体选取哪几样物品能得到最大价值，但只会输出一种状况
 
 * 0/1背包的降维，将空间复杂度降为O(V)
 // N表示物体的个数，V表示背包的载重
 //用于存储每一个物体的重量，下标从1开始
 //存储每一个物体的收益，下标从1开始
 //降成一维数组，用来保存每种状态下的最大收益
 //对一维数组F进行初始化
 //注意边界问题，i是从1开始的
 //打印全部结果，咱们要求的是F[V]
 * 第一行是物体个数、背包总空间；
 * 第二行是每一个物体的空间；
 * 第三行是每一个物体的收益。
 //下标从1开始，表示第1个物品

3.4 扩展——改为“刚好装满背包” 

 * 0/1背包问题变种：求刚好装满背包的最优解
 // N表示物体的个数，V表示背包的载重
 //用于存储每一个物体的重量，下标从1开始
 //存储每一个物体的收益，下标从1开始
 //降成一维数组，用来保存每种状态下的最大收益
 //注意边界问题，i是从1开始的
 //打印全部结果，咱们要求的是F[V]
 * 第一行是物体个数、背包总空间；
 * 第二行是每一个物体的空间；
 * 第三行是每一个物体的收益。
 //下标从1开始，表示第1个物品

我要回帖

更多关于 java程序分析题 的文章

 

随机推荐