0-1背包问题

有n件物品和一个最大承重为W的背包，每件物品的重量是w[i]，价值是v[i]
在保证总重量不超过W的前提下，选择某些物品装入背包，背包的最大总价值是多少？
注意：每个物品只有一件，也就是每个物品只能选择0件或者1件
分析：
假设：W=10，有5件物品，重量和价值如下：
w[1]=2,v[1]=6
w[2]=2,v[2]=3
w[3]=6,v[3]=5
w[4]=5,v[4]=4
w[5]=4,v[5]=6
dp数组的计算结果如下表：

image.png

i:选择i件物品 j:最大承重
解法：
dp方程：
如果：
可以选这一件物品
j > w[i]
不选：
dp(i,j) = dp(i - 1, j)

代码：

package com.david.alth.dp; 

/**
* 0-1背包 ，计算最大价值 
*/ 
public class Bag2 { 
    public static int maxValue(int[] values,int[] weights,int max){ 
        if(values == null || values.length == 0) return 0; 
        if(weights == null || weights.length == 0) return 0; 
        if(values.length != weights.length || max <= 0) return 0; 

        //dp数组 
        int[][]dp = new int[values.length+1][max+1];  
        for(int i = 1; i <= values.length; i++){ 
            for(int j = 1; j <= max; j++){ 
                //选择的物品超过最大承重
                if(j<weights[i-1]){ 
                    //最大价值=上一轮的最大价值（不选择该物品） 
                    dp[i][j]=dp[i-1][j]; 
                }
                //可选择该物品 
                else{
                    //上一轮的最大价值（不选择该物品） ，选择该物品 两者的最大值 
                    dp[i][j] = Math.max((dp[i-1][j]), values[i-1] + dp[i-1][j- weights[i-1]]); 
                } 
            } 
        }
        return dp[values.length][max]; 
    }
    
    public static void main(String[] args) { 
        int[] values={6,3,5,4,6}; 
        int[] weights={2,2,6,5,4}; 
        int max=10; 
        System.out.println(maxValue(values,weights,max)); 
    } 
}

时间复杂度为：O(i * j)
可以看出动态规划是计算的值是上次的某个值+这次的值
是一种用空间换时间的算法。