Jobdu-1123.采药0/1背包问题

Posted on | In

Question

题目描述：

辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。 为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。 医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。 我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

输入：

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。 接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出：

可能有多组测试数据，对于每组数据， 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入：

70 3 71 100 69 1 1 2

样例输出：

3

经典的背包问题

Answer

$dp[i][j]$ 总体积不超过 $j$ 的情况下，前 $i$ 个物品所能达到的最大价值

$dp[i][j] = \max (dp[i-1][j-weight[i]]+value[i], dp[i-1][j])$

dp[0][0] = 0

dp[0][j] = 0

逆序遍历状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int t = sc.nextInt();
            int m = sc.nextInt();
            int[][] dp = new int[101][1001];
            int[] needTime = new int[m + 1];
            int[] value = new int[m + 1];
            for (int i = 1; i <= m; i++) {
                needTime[i] = sc.nextInt();
                value[i] = sc.nextInt();
            }
            // initial dp
            for (int i = 0; i <= t; i++)
                dp[0][i] = 0;
            for (int i = 1; i <= m; i++) {
                for (int j = t; j >= needTime[i]; j--)
                    dp[i][j] = Math.max(dp[i - 1][j - needTime[i]] + value[i], dp[i - 1][j]);
                for (int j = needTime[i] - 1; j >= 0; j--) // can not load i
                    dp[i][j] = dp[i - 1][j];
            }
            System.out.println(dp[m][t]);
        }
    }
}

改进

$dp[j] = \max (dp[j-weight[i]]+value[i], dp[j])$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int t = sc.nextInt();
            int m = sc.nextInt();
            int[][] dp = new int[101][1001];
            int[] needTime = new int[m + 1];
            int[] value = new int[m + 1];
            for (int i = 1; i <= m; i++) {
                needTime[i] = sc.nextInt();
                value[i] = sc.nextInt();
            }
            // initial dp
            for (int i = 0; i <= t; i++)
                dp[0][i] = 0;
            for (int i = 1; i <= m; i++) {
                for (int j = t; j >= needTime[i]; j--)
                    dp[i][j] = Math.max(dp[i - 1][j - needTime[i]] + value[i], dp[i - 1][j]);
                for (int j = needTime[i] - 1; j >= 0; j--) // can not load i
                    dp[i][j] = dp[i - 1][j];
            }
            System.out.println(dp[m][t]);
        }
    }
}

以上是0-1背包问题，每一件物品至多只能选择一件，即在背包中该物品的数量只有0和1两种情况

变异1

要求所选择的物品必须恰好装满背包

dp[0][0] = 0

dp[0][j] = -inf or doesn’t exist

变异2–完全背包问题

每种物品的数量无限增加

有一个容积为V的背包，同时有 n 个物品，每个物品均有各自的体积w 和价值 v，每个物品的数量均为无限个，求使用该背包最多能装的物品价值总和

我们先按照 0-1 背包的思路试着求解该问题。设当前物品的体积为w，价值为 v，考虑到背包中最多存放 V/w 件该物品，我们可以将该物品拆成 V/w 件， 即将当前可选数量为无限的物品等价为 V/w 件体积为w、价值为 v 的不同物品。 对所有的物品均做此拆分，最后对拆分后的所有物品做 0-1 背包即可得到答案。 但是，这样的拆分将使物品数量大大增加

顺序遍历状态

1
2
3
4
5
for (int i = 1; i <= m; i++) {
    for (int j = needTime[i]; j <= t; j++)
        dp[j] = Math.max(dp[j - needTime[i]] + value[i], dp[j]);
}

complete code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int t = sc.nextInt();
            int m = sc.nextInt();
            int[] dp = new int[1001];
            int[] needTime = new int[m + 1];
            int[] value = new int[m + 1];
            for (int i = 1; i <= m; i++) {
                needTime[i] = sc.nextInt();
                value[i] = sc.nextInt();
            }
            // initial dp
            for (int i = 1; i <= t; i++)
                dp[i] = Integer.MIN_VALUE;
            dp[0] = 0;
            for (int i = 1; i <= m; i++) {
                for (int j = needTime[i]; j <= t; j++)
                    dp[j] = Math.max(dp[j - needTime[i]] + value[i], dp[j]);
            }
            System.out.println(dp[t]);
        }
    }
}