回溯

小猫爬山

https://ac.nowcoder.com/acm/contest/1014/A

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 105;
const int mod = 1e9 + 7;
int a[N], car[N];
int ans = 0x3f3f3f3f;
int n, w;
void dfs(int idx, int p) {
    if (p >= ans) return;
    if (idx == n + 1) {
        ans = min(p, ans);
        return;
    }
    rep(i, 1, p) if (car[i] + a[idx] <= w) {  // 可以上车
        car[i] += a[idx];
        dfs(idx + 1, p);
        car[i] -= a[idx];  // 回溯
    }
    if (idx != 1) {  // 单独放
        car[++p] = a[idx];
        dfs(idx + 1, p);
    }
}
int main() {
    scanf("%d%d", &n, &w);
    rep(i, 1, n) scanf("%d", a + i);
    dfs(1, 1);
    printf("%d", ans);
    return 0;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-17 14:38
干个蛋,干不了一点!!!!我真服了,还没搞完,很急。&nbsp;今天ddl,活没干完直接通宵,刺激。食堂很好吃,感觉离职的时候会胖10斤。mt喜欢能直接干活的,没空指导我,很难受。每个人都是笑嘻嘻的,但是从他们聊天中都能感受到各种试探,我有点慌了大家真的nb,都能准时完成工作下班,我羡慕啊!!!!!每天好累,想离职了💔
牛客26106072...:能去字节实习说明你的能力挺被认可的,实习中的这种累更有利于个人职场成长,试着当熬夜打游戏一样熬一熬,实习的意义就是看自己的差距和适应能力,总比等到工作时各种不适应辞职要好得多吧?
投递字节跳动等公司10个岗位
点赞 评论 收藏
分享
07-01 23:23
郑州大学 Java
否极泰来来来来:牛客迟早有高三的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务