动态规划---0-1背包

引言：0-1背包是算法考试中经常会出现的考题，因此掌握它的计算是十分有必要的，下面是自己学习0-1包的一些笔记，仅供参考：
一：问题提出：
给定n种物品和一个背包，物品i的重量是Wi,其价值为Vi,背包的容量为c。问应该如何选择装入背包的物品使得装入背包中的物品总价值最大？
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或者不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
此问题形式化描述为：给定c>0,Wi>0,Vi>0,1<=i<=n；找出n元0-1向量（x1,x2……xn），xi属于{0，1}1<=i<=n。

111.png

所以0-1背包问题就是一个特殊的整数规划问题：

222.png

1:最优子结构性质：
0-1背包问题具有最优子结构性质。设（y1,y2,y3,y4….yn）是所给0-1背包问题的一个最优解，则（y2,y3,y4….yn****）是下面相应子问题的一个最优解：

333.png
2:递归关系：
设所给的****0-1背包问题的子问题
444.png
的最优值为m(i,j),即m(i,j)是背包容量为j时，可以选择物品为i，i+1….，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m（i，j）递归式如下：
555.png
3：具体算法：

public class Package {
    //背包的容量
    private int weight;
    //一组物品的重量
    private int[] arrW;
    //相应物品的质量
    private int[] arrV;
    //表示当容量为j是的最大价值
    public int[][] c;
    //初始化这些值
    public Package(int length,int weight,int[] arrW1,int[] arrV1){
        this.weight =weight;
        arrV = new int[length+1];
        arrW= new int[length+1];
        c = new int[length+1][weight+1];
        //为了确保后面计算时从1开始，我们在初始化矩阵时需要注意
        for(int i=1;i<length+1;i++){
            arrV[i]=arrV1[i-1];
            arrW[i] = arrW1[i-1];
        }
    }
    public void solve(){
        //对物品进行循环
        for(int i=1;i<arrW.length;i++){
            //重量每一次增加1
            for(int j=1;j<=weight;j++){
                if(arrW[i]<=j){
                    c[i][j]= Math.max(c[i-1][j],c[i-1][j-arrW[i]]+arrV[i]);
                }else{
                    c[i][j] = c[i-1][j];  
                };
            }
        }
    }
//打印结果
    public void printResult(){
        for(int i=0;i<arrV.length;i++){
            for(int j=0;j<=weight;j++){
                System.out.print(c[i][j]+"            ");
            }
            System.out.println();
        }
    }
//测试用例
    public static void main(String[] args) {
        int[] v = {60,100,120};
        int[] w = {10,20,30};
        int weight=50;
        Package p = new Package(3,weight,w,v);
        p.solve();
        p.printResult();
    }
}