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

news/2024/7/20 22:52:01 标签: 剪枝, 算法, 深度优先, c++

没没没没没没没没没错,又是一道简单的递归,只不过加了剪枝,我已经不想再多说,这道题写了一开始写了普通深搜,然后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;
}


http://www.niftyadmin.cn/n/5213977.html

相关文章

『亚马逊云科技产品测评』活动征文|EC2 实例安装 docker 与配套软件部署前后端分离的医疗管理后台系统

授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚马逊云科技官方渠道 目录 一、AWS 产品类别选择 &#xff08;1&#xff09;应用服务器选择…

acwing算法基础之数学知识--Nim游戏和集合Nim游戏

目录 1 基础知识2 模板3 工程化 1 基础知识 &#xff08;一&#xff09; Nim游戏&#xff1a; n n n堆物品&#xff0c;每堆有 a i a_i ai​个&#xff0c;两个玩家轮流取走任意一堆的任意个物品&#xff0c;但不能不取。取走最后一个物品的人获胜。 结论&#xff1a;如果这n…

Lombok新版超全面使用教程

一、Lombok介绍 Lombok是一个Java库&#xff0c;可以通过注解来简化Java类的编写&#xff0c;减少冗余的样板代码。它提供了一系列的注解&#xff0c;用于自动生成常见的代码&#xff0c;如getter和setter方法、构造函数、equals和hashCode方法、toString方法等。通过使用Lomb…

测试Bard和ChatGPT对双休有关法规的认知和简单推理

Bard是试验品&#xff0c;chatgpt是3.5版的。 首先带着问题&#xff0c;借助网络搜索&#xff0c;从政府官方网站等权威网站进行确认&#xff0c;已知正确答案的情况下&#xff0c;再来印证两个大语言模型的优劣。 想要了解的问题是&#xff0c;在中国&#xff0c;跟法定工作…

FFmpeg命令分隔视频

有一个视频如a.mp4&#xff0c;此视频采用帧率为30生成&#xff0c;共有299帧&#xff0c;这里通过FFmpeg命令分隔成1秒一个个的小视频&#xff0c;即每个小视频帧数为30帧。 用到的FFmpeg参数如下所示&#xff1a; (1).-i:指定输入视频文件的名称&#xff1b; (2).-c:指…

Android Frameworks 开发总结之七

1.修改android 系统/system/下面文件时权限不够问题 下面提到的方式目前在Bobcat的userdebug image上测试可行&#xff0c;还没有在user上测试过. 修改前: leifleif:~$ adb root restarting adbd as root leifleif:~$ adb disable-verity verity is already disabled using …

Linxu 进程替换

进程替换的背景&#xff1a; 进程的替换我们需要调用execl这个接口,exxecl在3号手册&#xff0c;属于系统接口。 调用系统命令 execl 为了方便理解execl的作用&#xff0c;我们写一个程序&#xff1a; 单进程替换 我们发现运行结果是通过c库里的exec接口把系统命令 "l…

树的两种遍历

1 树的序遍历 前序遍历、中序遍历、后序遍历 1.1 遍历方式 都有点抽象&#xff0c;需要结合代码和画图来看 递归遍历非递归遍历&#xff1a;都是用栈来解决 前序遍历 用一个栈&#xff0c;先进右再进左 中序遍历 用一个栈&#xff0c;先进左&#xff0c;左出&#xff0c;再…