tianbiandetianbian
AlanJiang_NLP
采纳率54.5%
2018-04-21 10:19 阅读 2.3k
已采纳

用不同方式的递归来解决01背包问题的疑问

5

01背包问题,假设表示各个物品重量的数组为w,对应的价值为数组v,这里用两种方式进行解决,第一种方式:反向遍历,即我从后往前进行选择,即从w.length-1到0进行选择,第二种方式:正向遍历,从第0个物品开始往第w.length-1个物品开始决策,具体代码如下:
//方式一:反向遍历,即我从后往前进行选择,即从w.length-1到0进行选择,

 public class Knapsack {
    //表示各个物品的重量
  public static int w[];
    //表示各个物品的价值
   public static int v[];
   //表示背包容量
   public static int totalWeight;
   //用于存储计算过的子问题的解的二维数组
   public static int[][] tempArray;
    public static void main(String[] args) {
        w = new int[]{3, 4,5,2,7};
        v = new int[]{9,3,21,4,33};
        totalWeight = 15;
        int len = w.length;
        System.out.println(getSValue(len-1,15));
    }
    private static int getSValue(int index, int resiWeight) {
        //暴力搜索来获取的背包问题的最大价值,返回值 就是这个最大值,函数本身的含义表示选取到第index个物品时已经获得的价值,第二个参数表示背包还剩余的容量
        if (resiWeight<=0)
            return 0;
        if (index==-1)
            return 0;

        if (resiWeight>=w[index]) {
           return Math.max(getSValue(index - 1, totalWeight - w[index]) + v[index], getSValue(index - 1, resiWeight));
    }
        else {
            return getSValue(index-1,resiWeight);
        }

    }
}

//方式二:反向来写的话,即从第0个物品开始决策直到第w.length-1个物品,代码如下:

 public static int f(int cur,int max)
    {
        if(cur==num)//物品已经尝试完,这里必须是cur==num或cur<=num,说明决策到了第num-1个物品,已到数组的最后一个元素进行决策,不管怎么决策,将调用的是f(num),这个物品根本不存在,注意这里的判断是写在了递归式前面
            return 0;
        if(max<=0)//背包已经装满,没有容量了
            return 0;
        if(max<w[cur])//背包容量小于该商品的重量
            return f(cur+1,max);
        else
        {
            return Math.max(f(cur+1,max), f(cur+1,max-w[cur])+v[cur]);
        }
    }

上述两种方式应该都可以,但是正向方式得到的最大价值是70,明显是把所有物品都选了,才有70,但是重量和超过背包容量15,肯定有问题,不知到错在哪里,但是反向来写的话,即从第0个物品开始决策直到第w.length-1个物品,,,得到的结果是63,这个对的,为什么第一中方式的结果是错的,求大神解惑?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • 已采纳
    qq_32227619 小白_马 2018-04-21 12:25

    return Math.max(getSValue(index - 1, totalWeight - w[index]) + v[index], getSValue(index - 1, resiWeight));

    把里面的totalWeight改成resiWeight。你的函数参数是resiWeight,而不是totalWeight,如果按你写的,程序跑起来getSValue(index,resiWeight)的第二个函数参数值始终不变,所以始终有resiWeight>=w[index]

    点赞 评论 复制链接分享
  • ZWJ_0115 ZWJ_0115 2018-04-21 12:06

    在getSValue函数中:
    if (resiWeight>=w[index]) {
    return Math.max(getSValue(index - 1, totalWeight - w[index]) + v[index], getSValue(index - 1, resiWeight));
    你把resiWeight打成了totalWeight,应该是:
    return Math.max(getSValue(index - 1, resiWeight - w[index]) + v[index], getSValue(index - 1, resiWeight));

    点赞 2 评论 复制链接分享

相关推荐