RUC校内OJ #1014. H. 采购账单

小T老师最近为一堆采购物资的报账而烦恼！

采购$N$件物品，每件物品的价格为$P_i$。按照财务要求，每笔报账单可以包含无数件物品，但价格总和不超过$V$。

现在小T老师想知道，最多能报账多少金额。此外，在保证金额最多的前提下，最少分多少笔报账单。

第一行两个正整数：$N,V$

第二行$N$个正整数用空格隔开，表示每件物品的价格$P_i$

一行，两个正整数用空格隔开，分别表示最多金额和最少报账单数量。

【输入样例】

10 1000

468 796 72 121 346 160 401 967 228 361

【输出样例】

3920 4

$1\le N\le 60,1\le V\le 10,000,1\le P_i\le 10^9$

思路:肯定是搜索+剪枝优化.

搜索框架: 有两种比较经典的框架,一种是先搜索同一帐单的全部物品,另外一种是按照物品的顺序,考虑将物品放入哪一个帐单,或者新开一个.

如果做过一道叫木棒游戏的经典搜索题,就会知道前者往往比后者有更多的优化空间,事实证明如此.

方法一:(我的做法)

剪枝1: 把物品从大到小排序,优先放大的

剪枝2:如果当前分的帐单已经>=目前最优解,剪枝

剪枝3:每个帐单的第一个都选择目前最大的,因为这个物品必然会分给某个帐单

剪枝4:分完一个帐单以后需要确保不能再插入物品

剪枝5:考虑当前层里面的所有分法,如果有一种每个都比另外一种小,那么这个肯定不用

在加上剪枝5之前都会tle,加完以后每个点都只用2ms,快的飞起

#include <bits/stdc++.h>
using namespace std;const int N = 70;int n, m, a[N];
bool v[N];
int ans;
int b[N][N], c[N];bool cmp(int p1, int p2) { return p1 > p2; }//需要加的剪枝:对于某一层,如果数量有少,总数又少,就剪掉?void dfs(int k, int sum, int num, int tot, int layers) {  // sum: 当前总量 num:当前数量 tot:数量 layers:层数if (layers >= ans)return;if (tot == n) {ans = layers;return;}if (num == 0) {for (int i = k; i <= n; i++) {if (!v[i]) {v[i] = 1;c[num + 1] = a[i];dfs(i + 1, sum + a[i], num + 1, tot + 1, layers);v[i] = 0;break;}}} else {bool bk = 0;for (int i = k; i <= n; i++) {if (!v[i] && sum + a[i] <= m) {bk = 1;v[i] = 1;c[num + 1] = a[i];dfs(i + 1, sum + a[i], num + 1, tot + 1, layers);v[i] = 0;}}if (!bk) {for (int i = n; i >= 1; i--) {if (!v[i]) {if (sum + a[i] > m) {bk = 1;}break;}}if (bk) {bk = 0;for (int i = 1; i <= num; i++) {if (c[i] > b[layers][i]) {bk = 1;break;}}if (bk) {for (int i = 1; i <= num; i++) {b[layers][i] = c[i];}b[layers][num + 1] = 0;b[layers + 1][1] = 0;dfs(1, 0, 0, tot, layers + 1);}}}}
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;int ret = 0;int t = n;n = 0;for (int i = 1; i <= t; i++) {int x;cin >> x;if (x > m)continue;a[++n] = x;ret += x;}sort(a + 1, a + n + 1, cmp);ans = n;dfs(1, 0, 0, 0, 1);cout << ret << " " << ans << "\n";return 0;
}

方法二:学长的做法(极限数据500ms)

#include <bits/stdc++.h>
using namespace std;const int N = 70;int n, m, a[N];
bool v[N];
int ans;
int b[N][N], c[N];bool cmp(int p1, int p2) { return p1 > p2; }//需要加的剪枝:对于某一层,如果数量有少,总数又少,就剪掉?void dfs(int k, int sum, int num, int tot, int layers) {  // sum: 当前总量 num:当前数量 tot:数量 layers:层数if (layers >= ans)return;if (tot == n) {ans = layers;return;}if (num == 0) {for (int i = k; i <= n; i++) {if (!v[i]) {v[i] = 1;c[num + 1] = a[i];dfs(i + 1, sum + a[i], num + 1, tot + 1, layers);v[i] = 0;break;}}} else {bool bk = 0;for (int i = k; i <= n; i++) {if (!v[i] && sum + a[i] <= m) {bk = 1;v[i] = 1;c[num + 1] = a[i];dfs(i + 1, sum + a[i], num + 1, tot + 1, layers);v[i] = 0;}}if (!bk) {for (int i = n; i >= 1; i--) {if (!v[i]) {if (sum + a[i] > m) {bk = 1;}break;}}if (bk) {bk = 0;for (int i = 1; i <= num; i++) {if (c[i] > b[layers][i]) {bk = 1;break;}}if (bk) {for (int i = 1; i <= num; i++) {b[layers][i] = c[i];}b[layers][num + 1] = 0;b[layers + 1][1] = 0;dfs(1, 0, 0, tot, layers + 1);}}}}
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;int ret = 0;int t = n;n = 0;for (int i = 1; i <= t; i++) {int x;cin >> x;if (x > m)continue;a[++n] = x;ret += x;}sort(a + 1, a + n + 1, cmp);ans = n;dfs(1, 0, 0, 0, 1);cout << ret << " " << ans << "\n";return 0;
}