庆阳网站设计费用,定制网络零信任,wordpress简洁好用页脚代码,免费网站建站有哪些没没没没没没没没没错#xff0c;又是一道简单的递归#xff0c;只不过加了剪枝#xff0c;我已经不想再多说#xff0c;这道题写了一开始写了普通深搜#xff0c;然后tle了一个点#xff0c;后面改成剪枝#xff0c;就ac了#xff0c;虽然数据很水#xff0c;但是不妨…没没没没没没没没没错又是一道简单的递归只不过加了剪枝我已经不想再多说这道题写了一开始写了普通深搜然后tle了一个点后面改成剪枝就ac了虽然数据很水但是不妨碍我们练习搜索。
先画个草图 从1开始找找下一层最左边的2判断箱子里是否能装下这个物体如果能装进去。现在箱子里装了12 体积是8311
然后继续下一层继续判断能否装下。找最左边的3现在箱子里装了123 体积是831223
再找下一个4发现23724就是箱子装不下了那就跳过4往下搜。
当搜完了我们就返回上一层重复这个步骤即可。
上代码
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
#includenumeric
#includeiomanip
using namespace std;
const int N 307;
const int V 2e4 7;
int a[N];
int flag[N];
int n, v, ans0x7fffffff;
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;
}
