img

Janglejay

IT

傅芳杰

个人博客

You Deserve The Best

背包模型1

| 阅读：次

多重背包-单调队列优化

按照自己的理解说了一遍，心中还是有存疑，等之后看看会不会理解透再更新 6YuGV0.png

AcWing 6. 多重背包问题 III 原题链接

有 NN 种物品和一个容量是 VV 的背包。

第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。

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

输入格式

第一行两个整数，N，VN，V (0<N≤1000(0<N≤1000, 0<V≤20000)0<V≤20000)，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤10000<N≤1000 0<V≤200000<V≤20000 0<vi,wi,si≤200000<vi,wi,si≤20000

提示

本题考查多重背包的单调队列优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

朴素写法：

    private static void function1() {
        int n = in.nextInt();
        int m = in.nextInt();
        Goods[] gs = new Goods[n + 1];
        for (int i = 1; i < n + 1; i++) gs[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
        int[][] dp = new int[n + 1][m + 1];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
            int v = gs[i].volume;
            int w = gs[i].weight;
            int number = gs[i].number;
            //r : remainder
            for (int r = 0; r < v; r++) {
                list.clear();
                for (int k = 0; r + k * v <= m; k++) {
                    if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
                    while (!list.isEmpty() &&
                            dp[i - 1][r + k * v] - k * w >=
                                    dp[i - 1][r + list.getLast() * v] - list.getLast() * w
                    ) {
                        list.removeLast();
                    }
                    list.add(k);
                    dp[i][r + k * v] = dp[i - 1][r + list.getFirst() * v] + ((k - list.getFirst()) * w);
                }
            }
        }
        out.println(dp[n][m]);
        out.flush();
        out.close();
    }

空间优化写法：

    private static void function2() {
        int n = in.nextInt();
        int m = in.nextInt();
        Goods[] gs = new Goods[n + 1];
        for (int i = 1; i < n + 1; i++) gs[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
        int[] dp = new int[m + 1];
        int[] bak = new int[m + 1];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
            System.arraycopy(dp, 0, bak, 0, m + 1);
            int v = gs[i].volume;
            int w = gs[i].weight;
            int number = gs[i].number;
            //r : remainder
            for (int r = 0; r < v; r++) {
                list.clear();
                for (int k = 0; r + k * v <= m; k++) {
                    if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
                    while (!list.isEmpty() &&
                            bak[r + k * v] - k * w >=
                                    bak[r + list.getLast() * v] - list.getLast() * w
                    ) {
                        list.removeLast();
                    }
                    list.add(k);
                    dp[r + k * v] = bak[r + list.getFirst() * v] + ((k - list.getFirst()) * w);
                }
            }
        }
        out.println(dp[m]);
        out.flush();
        out.close();
    }

AcWing 1019. 庆功会 原题链接

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

输入格式

第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。

输出格式

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

数据范围

n≤500,m≤6000n≤500,m≤6000, v≤100,w≤1000,s≤10v≤100,w≤1000,s≤10

输入样例：

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

输出样例：

1040

    private static class Goods {
        private int price;
        private int value;
        private int number;

        public Goods(int price, int value, int number) {
            this.price = price;
            this.value = value;
            this.number = number;
        }
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        int m = in.nextInt();
        Goods[] goods = new Goods[n + 1];
        LinkedList<Integer> list = new LinkedList<>();
        int[] dp = new int[m + 1];
        int[] bak = new int[m + 1];
        for (int i = 1; i <= n; i++) goods[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
        for (int i = 1; i <= n; i++) {
            int value = goods[i].value;
            int price = goods[i].price;
            int number = goods[i].number;
            System.arraycopy(dp, 0, bak, 0, m + 1);
            for (int r = 0; r < price; r++) {
                list.clear();
                for (int k = 0; price * k + r <= m; k++) {
                    if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
                    while (!list.isEmpty() && bak[r + k * price] - k * value >=
                            bak[r + list.getLast() * price] - list.getLast() * value
                    ) {
                        list.removeLast();
                    }
                    list.add(k);
                    dp[r + k * price] = bak[r + list.getFirst() * price] + ((k - list.getFirst()) * value);
                }
            }
        }
        out.println(dp[m]);
        out.flush();
        out.close();
    }

AcWing 423. 采药 原题链接

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

输入文件的第一行有两个整数T和M，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。

接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出文件包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

数据范围

1≤T≤10001≤T≤1000, 1≤M≤1001≤M≤100

输入样例：

70 3
71 100
69 1
1 2

输出样例：

3

朴素写法：

    private static class Herb{
        private int time;
        private int value;

        public Herb(int time, int value) {
            this.time = time;
            this.value = value;
        }
    }
    private static void function1() {
        int t = in.nextInt();
        int n = in.nextInt();
        Herb[] herbs = new Herb[n + 1];
        for (int i = 1; i <= n; i++) {
            herbs[i] = new Herb(in.nextInt(), in.nextInt());
        }
        int[][] dp = new int[n + 1][t + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= t; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= herbs[i].time) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - herbs[i].time] + herbs[i].value);
                }
            }
        }
        out.println(dp[n][t]);
        out.flush();
        out.close();
    }

空间优化写法：

    private static class Herb{
        private int time;
        private int value;

        public Herb(int time, int value) {
            this.time = time;
            this.value = value;
        }
    }
    public static void main(String[] args) {
//        function1();
        function2();
    }
    private static void function2() {
        int t = in.nextInt();
        int n = in.nextInt();
        Herb[] herbs = new Herb[n + 1];
        for (int i = 1; i <= n; i++) {
            herbs[i] = new Herb(in.nextInt(), in.nextInt());
        }
        int[] dp = new int[t + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = t; j >= herbs[i].time; j--) {
                if (j >= herbs[i].time) {
                    dp[j] = Math.max(dp[j], dp[j - herbs[i].time] + herbs[i].value);
                }
            }
        }
        out.println(dp[t]);
        out.flush();
        out.close();
    }

AcWing 1024. 装箱问题 原题链接

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

数据范围

0<V≤200000<V≤20000, 0<n≤300<n≤30

输入样例：

24
6
8
3
12
7
9
7

输出样例：

0

    public static void main(String[] args) {
        int m = in.nextInt();
        int n = in.nextInt();
        int[] arr = new int[n + 1];
        int[] dp = new int[m + 1];
        for (int i = 1; i < n + 1; i++) arr[i] = in.nextInt();
        for (int i = 1; i < n + 1; i++) {
            for (int j = m; j >= arr[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
            }
        }
        out.println(m - dp[m]);
        out.flush();
        out.close();
    }

AcWing 1022. 宠物小精灵之收服 原题链接

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而，野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。

如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式

输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围

0<N≤10000<N≤1000, 0<M≤5000<M≤500, 0<K≤1000<K≤100

输入样例1：

10 100 5
7 10
2 40
2 50
1 20
4 20

输出样例1：

3 30

输入样例2：

10 100 5
8 110
12 10
20 10
5 200
1 110

输出样例2：

0 100

题目思路

6YuJaV.png

    private static void function2() {
        int number = in.nextInt();
        int power = in.nextInt();
        int n = in.nextInt();
        Pet[] pets = new Pet[n + 1];
        int[][] dp = new int[number + 1][power + 1];
        for (int i = 1; i < n + 1; i++) pets[i] = new Pet(in.nextInt(), in.nextInt());
        for (int i = 1; i < n + 1; i++) {
            for (int j = number; j >= pets[i].number; j--) {
                for (int k = power - 1; k >= pets[i].power; k--) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - pets[i].number][k - pets[i].power] + 1);
                }
            }
        }
        int num = dp[number][power - 1];
        int res = power - 1;
        for (int i = power - 1; i >= 0; i--) {
            if (num == dp[number][i]) res = i;
            else break;
        }
        out.println(num + " " + (power - res));
        out.flush();
        out.close();
    }