回溯
小猫爬山
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;
} 算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
投递阿里巴巴集团等公司10个岗位