题目描述

题目链接

样例

输入：
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出：
8

基本思路就是分别转为01背包、完全背包、多重背包这几类问题逐个解决 可以是 完全背包转多重背包，再全部转为01背包；也可以完全背包单独解，多重背包转01背包求解

朴素解法

package codefortopic.PackPro;

import java.util.Scanner;

/** 混合背包问题 朴素解法 */
public class MixPack01 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int V = sc.nextInt();
    int[][] arr = new int[N + 1][3];
    for (int i = 1; i <= N; i++) {
      arr[i][0] = sc.nextInt();//vi 体积
      arr[i][1] = sc.nextInt(); //wi 价值
      arr[i][2] = sc.nextInt(); // si 数量： -1 表示0-1 ；0 表示无限 ；>0：表示该使用上限次数
      if (i != N) sc.nextLine();
    }
    int[][] dp = new int[N + 1][V + 1];

    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= V; j++) {
        if (arr[i][2] == -1) {
          if (j >= arr[i][0]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - arr[i][0]] + arr[i][1]);
          else dp[i][j] = dp[i - 1][j];

        } else if (arr[i][2] == 0) {
          for (int k = 0; k <= j / arr[i][0]; k++) {
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * arr[i][0]] + k * arr[i][1]);
          }
        } else {
          for (int k = 0; k <= arr[i][2]; k++) {
            if (j >= k * arr[i][0])
              dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * arr[i][0]] + k * arr[i][1]);
          }
        }
      }
    }
    System.out.println(dp[N][V]);
  }
}

一维DP解法

• 完全转多重转01
• 多重转01

package codefortopic.PackPro;

import java.util.Scanner;

/**
 * 混合背包问题  一维dp 解法
 */
public class MixPack02 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int V = sc.nextInt();
    int[][] arr = new int[100000][3];
    int cnt = 1;
    for (int i = 1; i <= N; i++) {
      int v = sc.nextInt();
      int w = sc.nextInt();
      int s = sc.nextInt();
      if (s == -1) {
        arr[cnt][0] = v;
        arr[cnt][1] = w;
        arr[cnt][2] = s;//-1  01 背包
        cnt++;
      }
      if (s == 0) { // 0  完全背包
        s = V / v; //把完整背包转多重，统一到下面转成0 1
      }
      if (s > 0) { // >0 多重背包 要转 0 1 背包
        for (int k = 1; k <= s; k <<= 1) {
          arr[cnt][0] = v * k;
          arr[cnt][1] = w * k;
          arr[cnt][2] = -1;
          s -= k;
          cnt++;
        }
        if (s > 0) {
          arr[cnt][0] = v * s;
          arr[cnt][1] = w * s;
          arr[cnt][2] = -1;
          cnt++;
        }

      }

      if (i != N) sc.nextLine();
    }
    int[] F = new int[V + 1];
    for (int i = 1; i < cnt; i++) {

      // 0 1 pack
      for (int j = V; j >= 1; j--) {
        if (j >= arr[i][0])
          F[j] = Math.max(F[j], F[j - arr[i][0]] + arr[i][1]);
        else F[j] = F[j];
      }

    }
    System.out.println(F[V]);

  }
}

• 完全按完全算
• 多重转01

package codefortopic.PackPro;

import java.util.Scanner;

/**
 * 混合背包问题  一维dp 解法
 */
public class MixPack03 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int V = sc.nextInt();
    int[][] arr = new int[100000][3];
    int cnt = 1;
    for (int i = 1; i <= N; i++) {
      int v = sc.nextInt();
      int w = sc.nextInt();
      int s = sc.nextInt();
      if (s == -1) {
        arr[cnt][0] = v;
        arr[cnt][1] = w;
        arr[cnt][2] = 1;//-1 改1 表示  01 背包
        cnt++;
      }
      if (s == 0) { // 0  完全背包
        arr[cnt][0] = v;
        arr[cnt][1] = w;
        arr[cnt][2] = 0;//0
        cnt++;
      }
      if (s > 0) { // >0 多重背包 要转 0 1 背包
        for (int k = 1; k <= s; k <<= 1) { // 乘以2 是<<1 , 不是<<2
          arr[cnt][0] = v * k;
          arr[cnt][1] = w * k;
          arr[cnt][2] = 1;
          s -= k;
          cnt++;
        }
        if (s > 0) {
          arr[cnt][0] = v * s;
          arr[cnt][1] = w * s;
          arr[cnt][2] = 1;
          cnt++;
        }

      }

      if (i != N) sc.nextLine();
    }
    int[] F = new int[V + 1];

    for (int i = 1; i < cnt; i++) {
      // 0 1 pack
      if (arr[i][2] == 1) {
        for (int j = V; j >= 1; j--) {
          if (j >= arr[i][0])
            F[j] = Math.max(F[j], F[j - arr[i][0]] + arr[i][1]);

        }

      } else { // 完全pack

        for (int j = 1; j <= V; j++) {
          if (j >= arr[i][0])
            F[j] = Math.max(F[j], F[j - arr[i][0]] + arr[i][1]);

        }
      }
    }
    System.out.println(F[V]);

  }
}