CSP-何以包邮?

题目描述

新学期伊始,适逢顿顿书城有购书满 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分)

实际上就是分两种情况

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

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

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]);
            }
        }
    }
}

热门相关:超武穿梭   夫人你马甲又掉了   法医娇宠,扑倒傲娇王爷   法医王妃不好当!   无限杀路