动态规划之背包问题递归实现方法改进

今天在搜索关于动态规划算法背包问题的时候，发现了一个问题:
网上关于求在指定重量的情况下背包装最有价值的物品这个问题的算法实现时，发现其中的递归实现是存在问题的，但是网上很多博客都是直接转载而没有做验证，带来了一定困惑。
网上关于动态规划这一类问题的算法实现大概如下图所示：
在给定的values和weights数组情况下，这个递归实现输出是正确的，但是如果你修改了这两个数组其中的数据，你会发现输出结果有问题，例如如果你把values数组第一个元素由20修改为10，你会发现输出结果为150(分别取weight数组里的第0,1,2,3个元素)，但实际最大值应该为160(取weights数组里的2,3,5元素)
为什么会出现这个问题呢，原因就出在if(j>=weights[i])这里，当算法从最后一个元素开始遍历时，r1的取值由倒数第二个元素来决定，但是在最后一个元素重量为100的情况下，第二个元素在if(j>=weights[i])这个校验处是不会通过的，所以就相当于倒数第一个元素只能由倒数第二个元素的取值迭代得到，倒数第二个元素必须和倒数第一个元素绑定，但实际上倒数第一个元素可以有前面任意一个元素迭代得到，所以才会得出错误的答案
我这里在原算法的基础上做了一些修改，实现此类背包问题的递归实现:

public static int bagProblem(int i, int j) {

        int r = 0;
        if(i==-1){
            return 0;
        }
        //如果剩余空间大于所放的物品
        if (j>=weights[i]){
        	int index = i;
        	int r1 = 0;
        	while(index >=0) {
        		int r1 = Math.max(r1, bagProblem(--index,j-weights[i]) + values[i]); //放第i件
        	}
            int r2 = bagProblem(i-1,j);//不放第i件
            r = Math.max(r1,r2);
        }
        return r;

    }

关键点在于让物品的选取不再具有依赖性，而是可以随意组合，从而得到在满足背包所能容纳重量的情况下得到所装下物品的最大价值。