动态规划01背包问题

女爷i 2022-05-30 00:47 450阅读 0赞

做个笔记记录一下：

> 给定n种物品和一个容量为 C的背包，物品i的重量是w，其价值为v 。
> 
> 问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

动态规划的关键在于状态如何转移，首先，我们使用m\[i\]\[j\]来表示前i个商品放入容量为j的背包中所能获取的最大价值，对于第i个物品，就存在两个选项，放或者不放。那么，那么m\[i\]\[j\]的状态转移方程可以通过下面的方式得出：

if (j >= w[i - 1]) { m[i][j] = Math.max(m[i - 1][j - w[i - 1]] + v[i - 1], m[i - 1][j]); } else { m[i][j] = m[i - 1][j]; }

*  如果第i个商品的重量大于背包容量，自然的第i个商品是无法放入包中的，得出：
    
    > **m\[i\]\[j\] = m\[i-1\]\[j\]**
 *  如果第i个商品的重量小于背包容量，我们就需要判断是否需要将物品i放入包中，问题就变成了前i-1个商品放入容量为j-w\[i\]的包中所获取的最大价值m\[i-1\]\[j-w\[i\]\] 加上 第i个商品的价值v\[i\] 是否大于前i-1个商品放入容量为j的包中所获取的最大价值m\[i-1\]\[j\]，即：
    
    > **m\[i\]\[j\] = Math.max(m\[i - 1\]\[j - w\[i - 1\]\] + v\[i - 1\], m\[i - 1\]\[j\]);**

完整代码如下：

public class BagTest { 
    
        static void bag(int[] w, int[] v, int capacity) {
            int[][] m = new int[w.length + 1][capacity + 1];
            /** * m[i][j] 前i件物品，放入容量为j的背包可装的最大价值 */
            for (int i = 1; i <= w.length; i++) {
                for (int j = 1; j <= capacity; j++) {
                    if (j >= w[i - 1]) {
                        m[i][j] = Math.max(m[i - 1][j - w[i - 1]] + v[i - 1], m[i - 1][j]);
                    } else {
                        m[i][j] = m[i - 1][j];
                    }
                }
            }
            System.out.println(m[w.length][capacity]);
            for (int i = 0; i < w.length + 1; i++) {
                for (int j = 0; j < capacity + 1; j++) {
                    System.out.print(m[i][j] + "\t");
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            int[] w = {
       5, 4, 7, 2, 6};
            int[] v = {
       12, 3, 10, 3, 6};
            bag(w, v, 10);
        }
    }