集装箱问题 (POJ 1017)

这是算法设计课上老师出的一道思考题,查了一下来源,是 POJ的1017号题,出自 Central Europe 1996

问题描述

某工厂的产品的形状都是长方体,长和宽都相等, 高度都是H, 他们的长宽分别为 1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品使用一个 6*6*H 的长方体包裹包装然后邮寄给客户。工厂要尽量减小每个订单运送时的包裹数量,他们需要有一个程序帮他们解决这个问题。

输入数据

输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1 至6*6 这六种产品的数量。输入文件将以6个0组成的一行结尾。

输出要求

除了输入的最后一行6 个0 以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。

输入样例

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

输出样例

2
1

算法思路

这是一道纯模拟题,按一般思路就可以构造出通解程序。

  • 由于产品和包裹的高度都是H,所以只需要考虑平面上正方形的摆放方式;
  • 对于[6*6]、[5*5]、[4*4]的产品,每个包裹只能容纳一个这样的产品,所以箱子的数目至少有这类的产品个数的总和;
  • 对于装有[6*6]产品的包裹,已经没有额外的空间可以装其它产品;
  • 对于装有[5*5]产品的包裹,至少还可以装下11个[1*1]的产品;
  • 对于装有[4*4]产品的包裹,至少还可以装下5个[2*2]的产品(或每个[2*2]的产品等价为4个[1*1]产品);
  • 一个新的包裹至少可以放得下4个[3*3]的产品,如果有剩于空间,可分为三种情况:
  • 剩3个[3*3]的产品的空间,可以放下5个[2*2]与7个[1*1]的产品;
  • 剩2个[3*3]的产品的空间,可以放下3个[2*2]与6个[1*1]的产品;
  • 剩1个[3*3]的产品的空间,可以放下1个[2*2]与5个[1*1]的产品;
  • 如果还有空间,可用[1*1]的产品填充;
  • 一个新的包裹至少可以放得下9个[2*2]的产品,如果有剩于空间,可用[1*1]的产品填充;
  • 一个新的包裹至少可以放得下36个[1*1]的产品;
  • 统计所有的箱子数。

实现代码

#include <stdio.h>

#define ONE		0
#define TWO		1
#define THREE	2
#define FOUR	3
#define FIVE	4
#define SIX		5

int main(void) {
	int boxes[6] = { 0 };
	int index, flag;
	while (1) {
		// input
		for (index = flag = 0; index < 6; index++) {
			scanf("%d", &boxes[index]);
			flag += boxes[index];

		}

		if (!flag) // 0 0 0 0 0 0
			break;

		// init
		int box_num = 0, i;

		// 6*6 boxing
		box_num += boxes[SIX];
		// 5*5 boxing
		box_num += boxes[FIVE];
		// 4*4 boxing
		box_num += boxes[FOUR];

		// 1*1 boxing in 5*5
		for (i = 0; i < boxes[FIVE]; i++) {
			if (0 < boxes[ONE])
				boxes[ONE] -= 11;
		}

		// 1*1 and 2*2 boxing in 4*4
		for (i = 0; i < boxes[FOUR]; i++) {
			if (0 < boxes[TWO]) {
				boxes[TWO] -= 5;
				// instead 2*2 of 1*1 boxing in 4*4
				for (; boxes[TWO] < 0; boxes[TWO]++)
					if (0 < boxes[ONE])
						boxes[ONE] -= 4;
			} else
				boxes[ONE] -= 20;

		}

		// 3*3 boxing
		while (0 < boxes[THREE]) {
			boxes[THREE] -= 4;
			box_num++;
		}
		// 1*1 and 2*2 boxing in 3*3
		switch (boxes[THREE]) {
		case -3:
			boxes[TWO] -= 5;
			boxes[ONE] -= 7;
			break;
		case -2:
			boxes[TWO] -= 3;
			boxes[ONE] -= 6;
			break;
		case -1:
			boxes[TWO] -= 1;
			boxes[ONE] -= 5;
		}
		// instead 2*2 of 1*1
		if (boxes[TWO] < 0) {
			while (boxes[TWO]++)
				if (0 < boxes[ONE])
					boxes[ONE] -= 4;
		} else {
			// 2*2 boxing
			while (0 < boxes[TWO]) {
				boxes[TWO] -= 9;
				box_num++;
			}

			// 1*1 boxing in 2*2
			for (; boxes[TWO] < 0; boxes[TWO]++)
				if (0 < boxes[ONE])
					boxes[ONE] -= 4;
		}

		// 1*1 boxing
		while (0 < boxes[ONE]) {
			boxes[ONE] -= 36;
			box_num++;
		}

		printf("%d\n", box_num);

	}
	return 0;
}

以上代码通过 GCC 编译,已经被 POJ Accepted :)

下载地址:GoogleCode

注意:使用 Visual C++ 6.0 的同学,代码可能无法正常通过编译,请自行处理 :(

Python 绕过网站登陆

学校的教学文件系统是半封闭的,学生登陆后选择指定的教师目录才可以查看里面的文件,对于某些加密的文件列表还需要输入密码才可以登陆。学生可以通过链接下载那些公开课件等教学资源。但是系统并没有提供一个检索引擎供学生搜索教学文件系统里的所有资源。

经过一番摸索,我发现如果直接在地址栏引用特定的文件索引号(id),就可以下载该链接对应的文件。这一途径给我提供了一条思路:可以写一个爬虫程序将教学文件系统上的所有资源扒出来,列成一个目录。如果再配上 sqlite 就可以完成一个简单的搜索引擎。

Python 是非常适合完成这类任务的工具,于是简单地学习了一下。

对于一个新手来说,最大的障碍在于如何验证网站的登陆。教学文件系统的登陆是带验证码的,要在程序里直接模拟登陆还是有一定的难度。一个比较合理的办法是写一个GUI界面,让用户直接登陆,然后使用获得的 COOKIE 进行检索既然一定要用到 COOKIE,那么我想到一个更加直接的方法:将一个已经登陆系统的 COOKIE 复制到程序中,这样不就可以了?这很像黑客经常使用的 COOKIE 欺骗 手法,不过这招相当管用。对于这种一次性的工作,这种直接绕过登陆的方法效率最高了。

import urllib2
# do something before...
cookie = 'PHPSESSID=c694de6be36b1f8b03077f4e2ade94f1' #填写COOKIE
header = {'Cookie':str(cookie)}
request = urllib2.Request(url, headers = header)
response = urllib2.urlopen(request)
# do somthing after ...
response.close()

经过测试,这个方法很成功地绕过了网站登陆。但是在每次想更新列表的时候,需要使用新的可用的 COOKIE。还好这不是经常要做的工作,暂时可以接受。

解决 GoAgent 证书无效警告

GoAgent 是我当前首选的代理工具,除了稳定的速度,最给力的就是能在教育网实现穿墙。如果要说有什么不足的话,就是一个月一天只有1G的流量(每个GAE帐号),不嫌麻烦的话可以多申请几个,每个gmail帐户可以免费开通10个Application。

GoAgent 项目主页
http://code.google.com/p/goagent/
Goagent 是一个使用 Python 和 Google Appengine SDK 编写的代理软件,可以运行在Windows/Mac/Linux/Andorid/iTouch/iPhone/iPad上。

GoAgent 的配置方法很简单,需要拥有一个 Google 帐号,然后申请一个 GAE 空间,第一次申请 GAE 空间时需要用手机接收短信验证码。具体的操作可以参考 GoAgent 项目主页。

如果你在使用 GoAgent 时遇到证书无效问题,请按以下方法解决:

这里以Chrome浏览器为例,理论上只要证书正确导入系统,就可以了。

Ubuntu 系统:

  • 打开 Chrome 浏览器
  • 首选项 > 高级选项 > 管理证书…
  • 授权中心 导入 GoAgent/local 目录下的 CA.crt 证书
    (注意不要导入到 服务器 ,否则不起作用
  • 在 授权中心 找到 GoAgent CA 并点击 修改…
  • 修改信任设置为全部选中
  • 重启浏览器

Windows 系统:

  • 打开 Chrome 浏览器
  • 选项 > 高级选项 > 管理证书…
  • 导入证书 > 下一步 > 选择 GoAgent/local 目录下的 CA.crt 证书 > 下一步 > 选择 证书存储:浏览… > 受信任的根证书颁发机构 > 下一步 … > 完成
  • 重启浏览器

MAC 系统:

  • 双击 GoAgent/local 目录下的 CA.crt 证书导入到系统
  • 在 Launchpad > 实用工具 > 钥匙串访问 > 系统 中找到 GoAgent CA 并双击
  • 选择 信任 > 使用此证书时 > 总是信任
  • 重启浏览器
然后,恭喜你,自由了!F*GFW
2012/06/17 UPDATE:Windows 平台下大多情况其实是因为360或其它安全工具阻止了 goagent 自带的证书管理工具——certmgr.exe的运行,所以导致原本随goagent启动的证书导入过程失败而出现这个问题。这种情况只要把360黑名单中的certmgr.exe添加到白名单即可。
2012/09/11 UPDATE: 经过观察,还发现360之流会通过修改系统时间使证书失效,网页中提示证书过期多数是这种情况。这时候只需要将系统时间修改至当然时间即可。

配置 Android 开发环境

暑假的时候为了参加第二届 Android应用开发中国大学生挑站赛,自学了一点 Android 程序开发。以前没打算学 JAVA 的,没想到 Android 还是让我走了一朝(Android 应用使用 JAVA 作为程序开发语言)。

关于这个比赛让我最感兴趣的奖品居然是区域赛的参与奖——Android 背包——提交作品就有,何乐而不为!于是兴匆匆地下载开发工具折腾了起来。下面对配置 Android 开发环境的过程做一点记录,分享给大家。

下载 JRE 或 JDK

由于 Android 应用是使用 JAVA 作为开发语言的,所以需要 JAVA 的开发工具包来编译 .java 文件,生成 .class 字节码文件。同时,Android SDK 管理工具以及 Eclipse IDE 都是基于JRE 的程序,所以必须先下载安装 JRE 或 JDK。JRE/JDK 可以在 oracle 官方网站获得:

http://www.oracle.com/technetwork/java/javase/downloads/index.html

UPDATE: 经过测试,安装 Android SDK 的时候提示说 JRE 不足以完成 Android 应用开发,需要安装 JDK 才可以。

下载 Android SDK

开发 Android 应用需要使用 Android SDK,SDK即软件开发工具(Software Development Kit)。可以在 Android 官方网站获得:

https://developer.android.com/sdk/index.html

可以选择适合自己平台的安装包。

下载后得到 SDK 的基本平台工具,但不包括 API 和开发 Android 应用所需要的各种库文件。

下载 Android 开发平台及组件

  • Windows 用户可以运行 Android SDK 目录下的 SDK Manager.exe
  • Linux 用户可以运行 Android SDK 目录下的 tools/android

更新可用的软件包(Available packages),选择相应的 Android 平台并开始下载。

安装完毕后就可以进行 Android 应用的开发啦!

某说:“等等,这啥都没有叫我怎么开发呀?用什么来开发?”

实际上,JDK 和 Android SDK 已经包含开发 Android 应用所需要的全部工具了,你只是需要一个文本编辑器,把程序代码敲上去,然后用 Android SDK 和 JDK 提供的编译器、链接器等工具就可以把代码打包成最终可以运行在 Android 手机上的程序。但是这样学习大量的命令行,太烦琐了!于是我们需要一个集成开发环境来帮我们完成这些琐碎的事情。

下载及配置 IDE

IDE,即集成开发环境(Integrated Development Environment),提供了一系列的辅助工具帮助程序员自动完成一些简单机械的工作,例如编译、连接等。

Android 提供了基于 Eclipse IDE 的 Android 开发环境——ADT

安装 Eclipse

Eclipse 可以在 eclipse.org 获得,建议安装 Eclise Classic 版:

http://www.eclipse.org/downloads/

为了正确运行 Eclipse,需要先配置 Jdk 或者 Jre 环境。在此之前我们已经安装了 Jdk,所以无须担心这个问题。

安装 ADT

http://developer.android.com/sdk/eclipse-adt.html

ADT,Android 开发工具(Android Development Tools) 作为 Eclipse 的插件而存在,所以安装过程只需要在 Eclipse IDE 中即可完成。

  1. 启动 Eclipse;
  2. 选择菜单 Help > Install New Software…
  3. 单击 Add 按钮;
  4. 在 Add Repository 对话框中填上
  1. Name: ADT Plugin
  2. Location:
    https://dl-ssl.google.com/android/eclipse/
  • 单击 Ok;
  • 稍等一会,列表中出现 Developer Tools,单击 Select All 按钮选中所有项;
  • 单击 Next;
  • 在接来的窗口中确认并安装所选的项;
  • 重启 Eclipse;
  • 指定 Android SDK 目录,选择之前解压 SDK 的目录;
接下来,可以创建自己的 Android 项目了!

使用 DC++ 下载资源

很多同学不屑于使用免费的宿舍的校园网,指其网速慢,无法访问国外网站等等,转而使用一学期250块大洋的电信宽带。其实校园网也有很多优点的,其中之一就是鲜为人知的 DC++ 电影服务器,上面有一个 4.37TB 的高清电影节点和一个 1.38TB 的高清美剧节点(不断增加中)以及其它同学分享的各种资源。下载速度高达 10M/s!首先来普及一下:

什么是 DC++?

Wikipedia.orgDC++ is a free and open-sourcepeer-to-peer file-sharing client that can be used to connect to the Direct Connect network or to the ADCprotocol. It is developed primarily by Jacek Sieka, nicknamedarnetheduck.

DC++@中国站:DC++资源分享平台的出现完美的解决了FTP资源更新慢、下载慢,BT资源求种留种难,校园网被迅雷、Maze、Huntmine充斥大量不良资源等问题,是一个非常适合于中国高校网络发展现状的资源共享、节约校园网出口带宽的完美解决方案。 我们协会开设了开源的DC++中国交流平台,致力于推广DC++资源共享平台在国内高校的推广,从入门到精通,传授DC++服务器架设、管理维护技术,帮助定制客户端软件,以拥有一个资源极其丰富、飞速下载的健康教育网为最高目标。

 

如何使用 DC++ 资源?

由于 DC++ 是开源软件,所以有各种平台的衍生版。在 Linux 下有 Linux DC++,使用 Ubuntu 的同学可以直接在软件中心下载。Windows 用户可以使用 ApexDC++,这些都是免费的。

连接到服务器

安装完 DC++ 客户端软件后,就可以尝试连接到专有服务器啦!

下面演示 Linux DC++ 操作:

  1. Favorite Hubs > Add…
  2. [可选] Auto connect on startup(启动时自动连接该服务器)
  3. Name: (随便写)
  4. Hub address: (服务器地址,见下文)
  5. Description: (留空)
  6. 钩上 Nick,在右侧写上自己的昵称(将显示在用户列表中)
  7. 双击列表中刚刚添加的项目即可连接到服务器
ApexDC++ 以及其它 DC++ 客户端的操作大同小异,请自行摸索。

此外,附上最最重要的——厦门大学的DC++服务器地址(仅限教育网)

210.34.0.222

写到这里吧,我的电影下载完了,看电影去咯~

在 GCC 中使用 math.h

最近在学习算法设计课程,需要写一些 c 程序。算法作业免不了要用到 math.h 库:

#include <math.h>

但是在 Linux GCC 环境下一编译就会出现类似如下的错误:

make all
Building target: SAT
Invoking: GCC C Linker
gcc  -o"SAT"  ./src/SAT.o   
./src/SAT.o: In function `main':
/home/mutoo/workspace/c/SAT/Debug/../src/SAT.c:38: undefined reference to `pow'

原来是因为 math库被放在了动态链接库中,如果程序中需要用到它,在链接时需要加上 -lm 命令:

$ gcc filename.c -lm -o  filename

其中 -l<library> 是对<library>库的引用;而 m 就是 math库。

另外,对于 Eclipse  CDT 的用户,可以进行如下配置

  • 选择菜单:Project > Properties…
  • 在对话框左边找到:C/C++ Build > Settings
  • 在对话框右边找到:Tool Settings > GCC Linker > Libraries
  • 单击 Libraries(-l) 边上的 [+] 号,增加一项
m

接下来就可以正常使用 math 库了。