解题思路
新学期伊始,适逢顿顿书城有购书满 $x$ 元包邮的活动,小 $P$ 同学欣然前往准备买些参考书。
一番浏览后,小 $P$ 初步筛选出 $n$ 本书加入购物车中,其中第 $i$ 本($1 \\le i \\le n$)的价格为 $a_i$ 元。
考虑到预算有限,在最终付款前小 $P$ 决定再从购物车中删去几本书(也可以不删),使得剩余图书的价格总和 $m$ 在满足包邮条件($m \\ge x$)的前提下最小。
试帮助小 $P$ 计算,最终选购哪些书可以在凑够 $x$ 元包邮的前提下花费最小?
输入格式
输入的第一行包含空格分隔的两个正整数 $n$ 和 $x$,分别表示购物车中图书数量和包邮条件。
接下来输入 $n$ 行,其中第 $i$ 行($1 \\le i \\le n$)仅包含一个正整数 $a_i$,表示购物车中第 $i$ 本书的价格。
输入数据保证 $n$ 本书的价格总和不小于 $x$。
输出格式
仅输出一个正整数,表示在满足包邮条件下的最小花费。
数据范围
$70\\%$ 的测试数据满足:$n \\le 15$;
全部的测试数据满足:$n \\le 30$,每本书的价格 $a_i \\le 10^4$ 且 $x \\le a_1 + a_2 + \\cdots + a_n$。
输入样例1:
4 100
20
90
60
60
输出样例1:
110
样例1解释
购买前两本书 $(20+90)$ 即可包邮且花费最小。
输入样例2:
3 30
15
40
30
输出样例2:
30
样例2解释
仅购买第三本书恰好可以满足包邮条件。
输入样例3:
2 90
50
50
输出样例3:
100
样例3解释
必须全部购买才能包邮。
解题思路
法一($67 \text {ms}$)
每一个物品只能用一次,这是不是跟 $0 / 1$ 背包很像?
我们设 $f _ {i, j}$ 为 只用前 $i$ 个物品中的一些物品,物品总价格为 $j$ 的最小价值。
刚开始 $f _ {0, 0} = 0$,其它则为 $+ \infty$。考虑第 $i$ 个物品,有选和不选两种状态。如果不选,则 $f _ {i, j} = f _ {i - 1, j}$;如果选,则 $f _ {i, j} = f _ {i - 1, j - a _ i} + a _ i$。因此我们可得到状态转移方程 $f _ {i, j} = \min \{f _ {i - 1, j}, f _ {i - 1, j - a _ i} + a _ i\}$。最后答案等于 $\min \limits _ {i = x} ^ {x + 9999} \{f _ {n, i}\}$(题目保证 $a _ i \le 10000$)。
我们还可以用倒序循环来优化掉 $f$ 数组的第一维。
法二($54 \text {ms}$)
考虑到这题也跟 装箱问题 很像,我们设 bool
数组 $f _ {i, j}$ 表示 是否可以只用前 $i$ 个物品中的一些物品来得到总价值为 $j$。
刚开始 $f _ {0, 0} = 1$,其它则为 $0$。同法一,如果 $f _ {i - 1, j} == 1$ 或 $f _ {i - 1, j - a _ i} == 1$,那么 $f _ {i, j} = 1$;否则 $f _ {i, j} = 0$。最后我们将 $i$ 从 $x$ 开始枚举,如果 $f _ {n, i} == 1$ 则输出 $i$。
同样可以通过倒序循环来优化掉 $f$ 数组的第一维。
AC Code
法一($600 \text B$)
#include <cstdio>
#include <cstring>
#define N 35
#define M 310005
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n, m, ans, a[N], f[M];
int main ()
{
scanf ("%d%d", &n, &m);
memset (f, 0x3f, sizeof (f)), f[0] = 0, ans = 2e9;
for (int i = 1; i <= n; i ++)
{
scanf ("%d\n", &a[i]);
for (int j = m + 1e4; j >= a[i]; j --)
{
f[j] = min (f[j], f[j - a[i]] + a[i]);
}
}
for (int i = m; i < m + 1e4; i ++)
{
ans = min (ans, f[i]);
}
printf ("%d", ans);
return 0;
}
法二($500 \text B$)
#include <cstdio>
#define N 35
#define M 310005
using namespace std;
int n, m, a[N], f[M];
int main ()
{
scanf ("%d%d", &n, &m), f[0] = 1;
for (int i = 1; i <= n; i ++)
{
scanf ("%d", &a[i]);
for (int j = m + 10000; j >= a[i]; j --)
{
f[j] |= f[j - a[i]];
}
}
for (int i = m; ; i ++)
{
if (f[i])
{
printf ("%d", i);
return 0;
}
}
return 0;
}
感谢观看!
$$\href {/blog/content/29204/} {\color {Lime} {【寒假每日一题】题解}}$$
f[j] |= f[j - a[i]];
可以问一下 | 是什么意思吗
按位或
放一个 $1$ 月日历赠送链接:AcWing【集日历瓜分10000AC币活动】赠送1月日历!
以后不定时会在最新的题解的评论区放日历赠送(可能不只是 $1$ 月)
方法一中m+1e4 是啥意思呢
1e4=10000
m+1e4=m+10000
赠送链接是隐藏的,即链接是用
[文字](链接)
这种形态在 $\text {Markdown}$ 中出现的藏挺好hh
藏哪了啊?
法一最后答案前面
那个句号hhh
大佬,那个装箱问题用第二个做法怎么做啊。
我知道了,把 for (int i = m; ; i ++) 改成 for (int i = m; ; i –) ;
然后把数组开1e9就可以了。
还有个问题,这个是状态压缩dp吗。还没学过。
不用开到 1e9 啊
应该不是,状态压缩dp里面的位运算是每一位都有实际意义,jcwing大佬的解法2里面的位运算本质是逻辑或,和法1差不多
大佬 $\times$,蒟蒻 $\sqrt {}$
hahaha,我开始的时候数组开小了求了半天都没AC,好久没做dp的痛()
看$n <= 30$的范围,这题用暴搜也可以做吧
爆搜过$70%$样例
对的 有些样例还是TLE了
感觉不太行26*2^30
可以双向搜索
复制的题面公式格式是不对的吧,你一个一个加的$吗
不是,我是用一个油猴脚本(今天刚用)复制的
油猴上有脚本