1. 01背包

背包问题_2.pdf

Acwing 2. 01背包问题

01背包，不超过，最大价值
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
00输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

二维版本

1. f[i, j] 表示只从前i个物品中选，且总体积不超过v的所有选法的集合，其属性是价值最大值
2. 状态计算：只考虑前i件物品的情况下计算在所有体积下的选法的最大价值

考虑第i件物品，当前体积为j，

• 若j < v[i]，不能选当前物品 f[i][j] = f[i - 1][j]
• 若 j >= v[i] ，当前物品可选可不选，如果不选 f[i, j] = f[i - 1][j] ，如果选择 f[i, j] = f[i - 1][j - v[i]] + w[i]，结果为两者取Max
  1. 初始状态

当 i == 0时，意思是从前0件物品中选且总体积不超过j的最大价值，很显然，结果是0
Arrays.fill(f[0], 0) 可写可不写。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        //读入每一件物品的体积和价值
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        //状态定义
        int[][] f = new int[n + 1][m + 1];
        //状态计算
        //外层遍历物品
        for (int i = 1; i <= n; i++) {
            //内层遍历体积
            for (int j = 0; 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]);
            }
        }
        System.out.println(f[n][m]);
    }
}

一维版本

去掉 i 这一维，效果相当于滚动数组
f[j] = Math.max(f[j], f[j - v[i]] + w[i]

为什么一维情况下枚举背包容量需要逆序？
在二维情况下，状态f``[i][j]是由上一轮i`` - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

for(int i = 1; i <= n; i++) 
    for(int j = m; j >= 0; j--)
    {
        if(j < v[i]) 
            f[i][j] = f[i - 1][j];  // 优化前
            f[j] = f[j];            // 优化后，该行自动成立，可省略。
        else    
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后
    } 
//进一步，只有背包容量j >= v[i]时f[j]才会被更新，所以可进一步优化为
for(int i = 1; i <= n; i++)
{
    for(int j = m; j >= v[i]; j--)  
        f[j] = max(f[j], f[j - v[i]] + w[i]);
} 
//当执行完循环结构后，由于已经决策了所有物品，f[j]就是所有物品背包容量 j 下的最大价值。即一维f[j]等价于二维f[n][j]

//整体代码
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int[] f = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) 
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        }
        System.out.println(f[m]);
    }
}

进一步优化，不需要存储体积和价值，在循环时读入即可

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] f = new int[m + 1];
        for (int i = 0; i < n; i++) {
            int v = sc.nextInt(), w = sc.nextInt();
            for (int j = m; j >= v; j--)
                f[j] = Math.max(f[j], f[j - v] + w);
        }
        System.out.println(f[m]);
    }
}

01背包求方案数

AcWing 278. 数字组合
01背包，恰好装满，方案数
思路：
状态表示：f[i][j]表示从前i个数中选，总和恰好为j的所有方案的集和
状态属性：集和元素个数
状态计算：考虑第i个数选或不选
f[i][j] = f[i - 1][j] + f[i - 1][j - x]，条件是j >= x
初始化：f[0][0] = 1表示从0个数中选总和为0的方案数为1，即什么都不选。

import java.util.*;
public class Main {
    static final int N = 110, M = 10010;
    static int[][] f = new int[N][M];
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= x)
                    f[i][j] += f[i - 1][j - x];
            }
        }
        System.out.println(f[n][m]);
    }
}

// 去掉物品维
import java.util.*;
public class Main {
    static final int M = 10010;
    static int[] f = new int[M];
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            for (int j = m; j >= x; j--) {
                f[j] += f[j - x];
            }
        }
        System.out.println(f[m]);
    }
}

其它例题