[CF1132E]Knapsack【暴力搜索】

时间：2023-03-08 21:07:17

你有一个容量为\(w\)的背包，和\(8\)件物品，重量分别为\(1~8\)的整数，分别有\(cnt_1 ... cnt_8\)，求最大容量。

解法

笨蛋chh一开始打了一个背包模板乱搞压缩容量\(j\)状态，结果搞爆炸了。
但是无意之间把对拍暴力交上去之后，\(a\)掉了。
冷静分析题目，数据范围容量\(w\)非常的大，那么我们就从数据规模小的\(8\)入手。
每次枚举有当前物品放几个，然后暴力乱搞就过掉了。
事实证明：暴力出奇迹

瞎讲

我们其实做过\(01\)背包的容量压缩版，但是笨蛋\(chh\)就是调不对\(QwQ\)（蒟蒻太菜了），好像在洛谷比赛某一次出现过。

ac代码

\(*宣传一波：没有快读的代码是没有灵魂的\)

#include <bits/stdc++.h>
#define ms(a, b) memset(a, b, sizeof(a))
#define LL long long
using namespace std;
inline LL gll() {
    LL w = 0, x = 0;
    char ch = 0;
    while (!isdigit(ch)) w |= ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return w ? -x : x;
}
LL ans=0, w, a[15]
inline void dfs(int x, LL sum) {
    if (x == 9) {
        ans = max(ans, sum);
        return;
    }
    LL v = min((w - sum) / x, a[x]);
    for (int i = 1; i <= 9; i ++) //枚举当前物品放几件
        dfs(x + 1, sum + max((LL)0, (v--) * x));
}
int main() {
    w = gll();
    for (int i = 1; i <= 8; i ++) a[i] = gll();
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}

upd，这道题目还可以折半搜索，也就是搜完前一半匹配后一半。。。

相关文章