题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

样例

4 5
1 2
2 4
3 4
4 5

输出 ： 8

算法1

(动态规划) $O(n^m)$

动态规划问题，首先我们用闫式分析法列出大纲

          集合 :

          条件 ： 一般是 max(最大值),min(最小值),count(数量)


        状态转移方程

1. 首先我们根据提议可以读出这题的条件是在有限的容量中，选出最大价值。
2. 那么我们就可以考虑用递推的方式来表示状态转移方程
3. 首先我们选择第1，2，3.......n (n表示数量) 分别选第一个，第二个，第三个，到第n个(在满足容量的情况下)
4. 不难看出，这题的条件是求最大值所以，我们的条件是在所有集合中求出最大值

设f[i][j] 表示选第i个元素，在满足最大容量的情况下;
f[i][j] 可以划分成两个状态，选第i个的和不选第i个的，当j <= v[i] 时那么表示我们不能选取
f[i][j] = Math.max(f[1][j],f[2][j],f[3][j]); f[i][j] = f[i - 1][j - v[i]] + w[i] (f[i - 1]代表i的前一个元素)

我们可以把f[i][j] 划分成选第i个元素的 f[i][j - v[i]] + w[i] 和不选第i个的 f[i - 1][j];

根据样例得出的f[i][j]表格
f[i][j]
2 2 2 2 2
2 4 6 6 6
2 4 6 6 8
2 4 6 6 8

时间复杂度 0(n * m)

Java 代码

import java.util.*;

public class Main {
    static int N = 1010;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt() , m = sc.nextInt();
        for (int i = 1 ; i <= n ; i ++ ) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1 ; i <= n ; i ++ ) 
            for (int j = 1 ; j <= m ; j ++ ) {
                f[i][j] = f[i - 1][j];
                if (j >= v[i]) f[i][j] = Math.max(f[i][j] , f[i - 1][j - v[i]] + w[i]);
            }
        for (int i = 1 ; i <= n ; i ++ ) {
            for (int j = 1 ; j <= m ; j ++ ) System.out.printf("%d ",f[i][j]);
            System.out.println();
        }
        System.out.println(f[n][m]);    
    }
}

算法2

(一维数组优化空间复杂度) $O(n^2)$

blablabla

时间复杂度

参考文献

Java代码

import java.util.*;

public class Main {
    static int N = 1010;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[] f = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt() , m = sc.nextInt();
        for (int i = 1 ; i <= n ; i ++ ) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1 ; i <= n ; i ++ ) 
            for (int j = m ; j >= v[i] ; j -- ) { 
            /* 这里从大大小遍历，因为用小到达会覆盖前一个的元素，
            边界条件大于v[i]那么我们就不需要在选取的时候判断边界条件
            */
               f[j] = Math.max(f[j] , f[j - v[i]] + w[i]);
            }

        System.out.println(f[m]);    
    }
}