洛谷P1049装箱问题 ————递归+剪枝+回溯

没没没没没没没没没错，又是一道简单的递归，只不过加了剪枝，我已经不想再多说，这道题写了一开始写了普通深搜，然后tle了一个点，后面改成剪枝，就ac了，虽然数据很水，但是不妨碍我们练习搜索。

先画个草图：

从1开始找，找下一层最左边的2，判断箱子里是否能装下这个物体，如果能，装进去。（现在箱子里装了（1，2） 体积是（8+3=11）

然后继续下一层继续判断，能否装下。（找最左边的3，现在箱子里装了（1，2，3） 体积是（8+3+12=23）

再找下一个，4，发现23+7>24，就是箱子装不下了，那就跳过4，往下搜。

当搜完了，我们就返回上一层重复这个步骤即可。

上代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
const int N = 30+7;
const int V = 2e4 + 7;
int a[N];
int flag[N];
int n, v, ans=0x7fffffff;
void dfs(int x, int v) {ans = min(ans, v);for (int i = x; i < n; i++) {if (flag[i] == 0) {if (v - a[i] >= 0) {flag[i] = 1;dfs(i + 1, v - a[i]);flag[i] = 0;}}}
}
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> v >> n;for (int i = 0; i < n; i++)cin >> a[i];dfs(0, v);cout << ans;
}