01背包问题的动态规划解法 |
您所在的位置：网站首页 › excel规划求解最优风险组合是什么 › 01背包问题的动态规划解法 |
01背包问题的动态规划解法
|
1. 问题描述： 有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。 1≤n≤100 1≤wi，vi≤100 1≤W≤10000 输入: n=4 (w,v)={(2,3),(1,2),(3,4),(2,2)} W=5 输出: 7（选择第0，1，3号物品） （因为对每个物品只有选和不选两种情况，所以这个问题称为01背包） 2. 我们可以使用普通递归或者记忆性递归来解决这个问题，下面我们采用动态规划的典型方式来进行解决，动态规划最重要的是要发现其中的规律，找出相应的dp公式，然后接下来的代码就比较容易了 我们一开始可以对其中的测试样例进行简单的分析，这里我们可以使用excel表格来帮助我们更好地展现其中的过程
上面这个表格可以帮助我们很好的理解其中的过程，背包的容量可以为0,1,2,3,4,5每一次都可以对当前物品进行选择或者不选， 物品编号表示当前可以选择的物品的范围，例如2代表我们可以0~2号这个范围的物品，其中选择的过程设计到两个变量在进行变化，一个是物品的选择范围，另外是可以选择的剩下的物品质量，所以这里我们采用二维数组这种数据结构来记录中间的过程 选择的过程实际上也是对于当前背包容量的多种组合求解出其中的最大价值的过程，这里可以通过观察表格的数据得到，用二维数组通过循环中去寻找，那么求解出的改行该列的二维数组的值代表当前可以选择的物品编号的范围中价值最大的，那么循环结束之后最后求解出来的就是我们需要求解的最大价值 对于当前的物品我们可以选择拿取或者不拿取，那么实际上就是组合的过程，假如对于当前的物品拿取了，那么背包的剩下容量我们需要往上一行背包的容量减去当前拿取物品的质量的上一列，把两个价值加起来，并且与不拿取当前物品的价值进行比较求解出最大值，不拿取当前物品的价值为上一行同一列的价值 3. 具体的代码如下： import java.util.Scanner; import static java.lang.Math.max; public class Main{ static int n; static int w[]; static int v[]; static int W; static int rec[][]; //使用二维数组来进行记录中间的过程 //使用dp公式 //其中使用Excel表格来进行dp公式的推导是非常有利的 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); w = new int[n]; v = new int[n]; for(int i = 0; i < n; i++){ w[i] =sc.nextInt(); } for(int i = 0; i < n; i++){ v[i] =sc.nextInt(); } W = sc.nextInt(); rec = new int[n][W + 1]; int res = dp(); System.out.println(res); sc.close(); } private static int dp(){ //初始化数组的第一行 for(int i = 0; i < W + 1; i++){ //注意是w[0]不是w[i]; if(i >= w[0]){ //注意是v[0]不是v[i]; rec[0][i] = v[0]; } } for(int i = 1; i < n; i++){ for(int j = 0; j < W + 1; j++){ if(j >= w[i]){ //特别要注意下标要写对 //dp实际上也是对几个组合中最大价值的求解 //假如能够拿取那么剩下的重量应该去上一行剩下的质量那一列去找 //dp公式实际上也是对多种组合求解最大价值的解决方式 //该一行代表的是多种组合之中背包容量的最大价值 rec[i][j] = max(v[i] + rec[i - 1][j - w[i]], rec[i - 1][j]); }else{ rec[i][j] = rec[i - 1][j]; } } } return rec[n - 1][W]; } }
|
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |