多重背包、混合背包、二维背包

多重背包、混合背包、二维背包

DP

多重背包

描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件,每件体积是 $v_i$,价值是 $w_i$。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

public class Beg_Multiple {
  final static int N = 10010;
  final static int[] f = new int[N];
  final static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));


  private static int get() throws IOException {
    cin.nextToken();
    return (int) cin.nval;
  }

  public static void main(String[] args) throws IOException {
    int n = get(), m = get();

    int idx = 0, k = 1;
    int[] v = new int[n * 11], w = new int[n * 11];
    for (int i = 0; i < n; i++) {
      int a = get(), b = get(), s = get();
      // 快速幂
      while (s < k) {
        v[idx] = a * k; w[idx++] = b * k;
        s -= k; k <<= 1;
      }
      if (s > 0) {
        v[idx] = a * s; w[idx++] = b * s;
      }
    }

    // 01 背包问题
    for (int i = 0; i < idx; 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]);
  }
}

混合背包

描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

物品一共有三类:

  • 第一类物品只能用 1 次(01背包);
  • 第二类物品可以用无限次(完全背包);
  • 第三类物品最多只能用 $s_i$ 次(多重背包);

每种体积是 $v_i$,价值是 $w_i$

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

public class Beg_Mix {
  final static int N = 10010;
  final static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  final static int[] f = new int[N];

  private static int get() throws IOException {
    cin.nextToken();
    return (int) cin.nval;
  }

  public static void main(String[] args) throws IOException {
    int n = get(), m = get();

    int idx = 0;
    int[] t = new int[N], v = new int[N], w = new int[N];
    for (int i = 0; i < n; i++) {
      int a = get(), b = get(), c = get();

      if (c <= 0) {
        v[idx] = a; w[idx] = b; t[idx++] = c;
      } else {
        for (int k = 1; k <= c; k <<= 1) {
          c -= k;
          v[idx] = a * k; w[idx] = b * k; t[idx++] = -1;
        }
        if (c > 0) {
          v[idx] = a * c; w[idx] = b * c; t[idx++] = -1;
        }
      }
    }

    for (int i = 0; i < idx; i++) {
      if (t[i] == 0)
        for (int j = v[i]; j <= m; j++)
          f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
      else
        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]);
  }
}

二维背包

描述

有 $N$ 件物品和一个容量是 $V$ 的背包,背包能承受的最大重量是 $M$。

每件物品只能用一次。体积是 $v_i$,重量是 $m_i$,价值是 $w_i$。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。

public class Beg_TwoDimensional {
  final static int N = 10010;
  final static int[][] f = new int[N][N];
  final static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

  private static int get() throws IOException {
    cin.nextToken();
    return (int) cin.nval;
  }

  public static void main(String[] args) throws IOException {
    int n = get(), v = get(), m = get();

    for (int i = 0; i < n; i++) {
      int a = get(), b = get(), c = get();

      for (int j = v; j >= a; j--)
        for (int k = m; k >= b; k--)
          f[j][k] = Math.max(f[j][k], f[j - a][k - b] + c);
    }

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

分组背包

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。

每件物品的体积是 $v_$,价值是 $w_$,其中 $i$ 是组号,$j$ 是组内编号。

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

public class Beg_Group {
  final static int N = 110;
  final static int[] f = new int[N], v = new int[N], w = new int[N];
  final static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

  private static int get() throws IOException {
    cin.nextToken();
    return (int) cin.nval;
  }

  public static void main(String[] args) throws IOException {
    int n = get(), m = get();

    for (int i = 0; i < n; i++) {
      int s = get();
      for (int j = 0; j < s; j++) {
        v[j] = get(); w[j] = get();
      }
      for (int j = m; j >= 0; j--) {
        for (int k = 0; k < s; k++)
          if (j >= v[k])
            f[j] = Math.max(f[j], f[j - v[k]] + w[k]);
      }
    }
    System.out.println(f[m]);
  }
}

参考