题目描述

新学期伊始，适逢顿顿书城有购书满 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 =x时的实际最小值，实际就是在求ex范围内的最大值        int target = sum - x;        int[] dp = new int[target + 1];        for (int i = 0; i = 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 = x && now + a[i] < ans) {                ans = now + a[i];            } else if (now + a[i] < x) { // 搜寻下一本书                dfs(i + 1, now + a[i]);            }        }    }}