題目描述
新學期伊始，適逢頓頓書城有購書滿 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]);
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552118.html
標籤：其他
上一篇：Windows的Mysql5.7社區版的安裝詳細操作，從無到有，安裝配置一條龍服務。（壓縮包自行安裝，非installer安裝）
下一篇：返回列表