CSP-何以包邮？

2023-05-11 00:27 由 Kitorio 发表于 #其他

题目描述

新学期伊始，适逢顿顿书城有购书满 x 元包邮的活动，小 P 同学欣然前往准备买些参考书。
一番浏览后，小 P 初步筛选出 n 本书加入购物车中，其中第 i 本（1≤i≤n）的价格为 ai 元。
考虑到预算有限，在最终付款前小 P 决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 m 在满足包邮条件（m≥x）的前提下最小。

试帮助小 P 计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n 和 x，分别表示购物车中图书数量和包邮条件。

接下来输入 n 行，其中第 i 行（1≤i≤n）仅包含一个正整数 ai，表示购物车中第 i 本书的价格。输入数据保证 n 本书的价格总和不小于 x。

输出格式

输出到标准输出。

仅输出一个正整数，表示在满足包邮条件下的最小花费

思路

这个题目通常可能会考虑回溯的做法，然而这种方法很容易超时。这里先放满分解法：转换为01背包。

01背包（建议理解）

初看这题的时候可能觉得背包容量难以确定，但可以反向思考。

这里设书籍的总价值为sum，我们所要求的答案为ans，而除去ans包含书籍的剩下的书籍的价值为ex = sum-ans。显然易见的，ans >= x，那么ans能取到的最小值就是x。那么ex的范围则可以确定为[0,sum-x]。

此时问题就可以转为求ex在其取值范围内的最大值，因为当ex取到最大值时，我们就可以得到想要的ans。此时背包的容量就等于sum-ex，书籍的价值与质量相等，成功转换为01背包问题。

import java.io.*;

public class Main {
    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        sc.nextToken();
        int n = (int) sc.nval;
        sc.nextToken();
        int x = (int) sc.nval;
        int[] a = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sc.nextToken();
            a[i] = (int) sc.nval;
            sum += a[i];
        }
        // 转化为01背包问题，即求在sum-x范围内能取得的最大价值
        // 将所有书籍的总价视为ans + ex = sum，其中ans可以取到的最小值为x，那么ex的范围就在[0,sum-x]
        // 求得了ex的范围，那么想要取得ans>=x时的实际最小值，实际就是在求ex范围内的最大值
        int target = sum - x;
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= a[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j - a[i]] + a[i]);
            }
        }
        out.println(sum - dp[target]);
        out.flush();
    }
}

回溯（只有95分）

实际上就是分两种情况

选择这本书，达到了包邮条件，而且还比当前值更小，更新
选择这本书，不够包邮，继续看下一本书。

并且要注意要从当前这本书的下一本书计算，不然容易重复判断

import java.io.*;

public class Main {
    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(System.out);

    static int n, x;
    static int ans = Integer.MAX_VALUE;
    static int[] a = new int[31];

    public static void main(String[] args) throws IOException {
        sc.nextToken();
        n = (int) sc.nval;
        sc.nextToken();
        x = (int) sc.nval;
        for (int i = 0; i < n; i++) {
            sc.nextToken();
            a[i] = (int) sc.nval;
        }
        dfs(0, 0);
        out.println(ans);
        out.flush();
    }

    static void dfs(int pos, int now) {
        if (ans == x)
            return;
        for (int i = pos; i < n; i++) {
            if (now + a[i] >= x && now + a[i] < ans) {
                ans = now + a[i];
            } else if (now + a[i] < x) { // 搜寻下一本书
                dfs(i + 1, now + a[i]);
            }
        }
    }
}