vlambda博客
学习文章列表

“

是一个经典的动态规划题目。

1. 问题描述

现在有四个物品，小偷的背包总容量是8，怎么样偷得物品是最大价值的？

假设现在有4种物品：

2. 问题分析

假设函数 f(k,w)：当背包容量为w，现有k件物品可以偷，所能偷到的最大价值。

以 f(4,8) 为例，也就是说4件物品，8的容量

由上面可以得到最大价值为12。

而且我们还可以知道状态转移方程应该怎么列。

如果我们获得了最大价值的情况，我们怎么知道背包装了什么物品呢？回溯

主要是基于状态转移方程来逆推，比如我们最后得到的f(4,8)=12,如果4号物品没有被偷，那么他应该和f(3,8)相等，但是，这里根据表格可以看到，两者不等，说明4号物品已经确认偷了；偷了4号物品，背包容量就剩下3，这是我们就要看f(3,3)了，判断第3个物品有没有被偷，方法一样，他跟f(2,3)是一样的，说明没有被偷....

3. 代码解法

public class KnapsackProblem {
    public static void main(String[] args) {
        // 这是一个二维数组，用来存储当前物品及重量下的最大价值
        int[][] f = new int[5][9];
        // 5个物品 对应的重量以及价值
        int[] w = {0,2,3,4,5};
        int[] v = {0,3,4,5,8};

        // 根据状态转移方程来填写前面声明的二维数组，自底向上
        for (int i = 1; i < 5; i++) {
            for (int j = 1; j < 9; j++) {
              // i为容量，j为价值
              // 当前物品的重量太大，装不下
              if (w[i]>j){
                  f[i][j] = f[i-1][j];
              }else{
                  // 可以装得下，装还是不装，哪个能获得的价值最大
                  f[i][j] = Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
              }
            }
        }
        // 输出4个物品和8个容量的最大价值
        System.out.println(f[4][8]);
    }
    // 回溯自己想
}

如何回溯呢？

public class KnapsackProblem {
    //int[] w = {1,4,3};
    //int[] val = {1500,3000,2000};
    static int[][] f = new int[5][9];
    static int[] w = {0,2,3,4,5};
    static int[] v = {0,3,4,5,8};
    static int[] object = new int[5];

    static void Dynamic(){
        //int i,j;
        for (int i = 1; i < 5; i++) {
            for (int j = 1; j < 9; j++) {
                if (w[i]>j){
                    f[i][j] = f[i-1][j];
                }else{
                    f[i][j] = Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

                }
            }
        }
        System.out.println(f[4][8]);
    }

    static void Find(int i,int j){
        // 说明回溯结束或者一开始就是0
        if (i == 0){
            System.out.println("装包物品为：");
            for (int i1 = 0; i1 < 5; i1++) System.out.print(object[i1]+" ");
            return;
        }
        // 如果没有偷
        if (f[i][j] == f[i-1][j]){
            object[i] = 0;
            Find(i-1,j); // 递归
        // 如果偷了当前的
        }else if (f[i][j] == f[i-1][j-w[i]]+v[i]){
            object[i] = i;
            Find(i-1,j-w[i]);
        }
    }

    public static void main(String[] args) {
        Dynamic();
        Find(4,8); // 偷的是2，4号物品
    }
}