洛谷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; }