前一段时间受别人之托帮他做数据结构的大作业。这个项目的要求是这样的：

• 排产满足订单需求：产品的单位是片，但是是按照批次来包装的，每个批次的量可能不同，而且批次是不可拆分的。比如一个批次有25片，订单需求是20片，那么就只能用这25片去fulfill订单而不可以拆成20片和5片。

• 假设有很多订单需要用很多批次来fulfill，有没有什么现成的算法可以合理的进行分配。也就是说要fulfill订单（配给订单的产品片数在订单的需求量的容差范围之内，比如上下1％），但是差异的量最小（即最接近订单的需求量）。 

• 比如我有订单A，B需求量分别为50，100片， 现在有批次

x1:20片

x2:20片

x3:25片

x4:25片

x5:20片

x6:21片

x7:21片

合理的配法是x3,x4配给订单A，其它的配给订单B。

• 考虑：如果有几千个批次几百张订单

    简单地说这个程序所要实现的是对资源进行"最合理"的分配。所谓“最合理”的分配，主要是以下几个指标：首先要能完成最大数量的订单其次完成最大的订单产量。在以上两个指标相同的基础上浪费的批次数和批次产量越小越好。点击查看具体的要求及数据格式。

    再看一下评分标准，蛮有新意的。

•  采用竞争得分的方式(winner-first)

假设20组程序，最高分10分，最低分1分，所有组分数之和不超过110分
20组结果相差不大：每个组5.5分
1组显著好于19组：最好组10分，其余组5.2分(=(110-10)/(20-1))
2个组显著好于18组，2个组之间有一定差异：最好组10分，第二组8分，其余组5.1分(=(110-18)/(20-2))
2个组显著好于18组，2个组之间无差异：最好组10分，其余组5分(=(100-20)/(20-2))

     如果你有兴趣尝试一下，可以把你的算法和结果告诉我，看一下谁的分配更“合理”。

       Java在Internet上的应用已经日渐普遍，使用在网页上的Java程序称之为applet，利用Applet的嵌入能够使原本静态的HTML富有变化，并且能够做到"声"、"动"、活泼的页面。

因为applet是从远端服务器上下载并且在本地执行，所以安全成为至关重要的一个话题。如果用户允许浏览器运行java程序，浏览器会下载并且立刻运行网页中包含的全部applet。用户没有机会来确认或者停止运行单独一个applet。正是因为这个原因，applet（不同于应用程序）的行为受限制。当applet试图违反一条访问规则时，applet安全管理器（applet security manager）会抛出SecurityException异常。

限制applet的执行环境常常被称为“沙箱”。在沙箱中运行的applet不能修改或者探测用户系统。

Java“沙箱”是运行Java小应用程序的一个软件单元，对Java小应用程序的访问权限加以限制，防止它访问计算机的关键部分，如磁盘驱动器、网络套接口和内存区。Java“沙箱”由三部分组成：字节码检验器、类装载器和安全管理器，这三部分共同完成装载和运行时对Java Applet的检验，用以限制对文件系统和网络的访问以及对浏览器内部的访问。

applet在“沙箱”中的默认安全策列如下：

l         Applet 不能运行任何本地可执行程序。

l         除了存放被下载的applet的服务器外，applet不能和其他主机通信。该服务器通常被称为“源主机”（originating host），这条规则常常被称为“applet仅仅允许和家里通信”(applet can only phone home)。这条规则保证applet不可能探测内部网络资源。

l         Applet只能读取它的代码基和任何子目录中的文件。

l         除了使用的Java版本，操作系统的名字和版本，系统使用的特殊字符（例如用来分隔文件的是/还是\，分隔路径的是: 还是;，分行的是\n还是\r\n）外，applet不能获取其他有关本地计算机的信息。特别是，applet不能找到用户名，e-mail地址等等信息。

l         Applet的弹出式窗口会带有一个警告信息。

正是因为applet是在Java虚拟机中解释运行，而不是由用户计算机的CPU运行，才使得这些安全规则成为可能。因为解释器会检查所有关键指令和程序运行范围，才能防止恶意编写（或是编写得糟糕）的applet不会导致计算机崩溃，重写系统内存或者是改变操作系统赋予的权限。

Java安全模型提供字节码验证器(Byte-CodeVerifier)、applet类装载器(ClassLoader)以及安全管理器(SecurityManager)来实现以上applet安全策列。这三者结合起来可在applet的装载与执行阶段，对文件系统、网络与浏览程序的内部存取做进一步检查。这三者相互充，缺一不可，共同维护着Javaapplet的安全。
    ●类装载器 　　

applet是作为一个Web主页的一部分执行的，为了装载applet，浏览器需要调用Javaapplet类装载器。类装载器能够确定applet何时以及如何装载类（即代码）。它的主要功能包括：
　　．从远程机器上开载applet代码 　　

．创建和实施一个名称空间分级，以确保运行的applet不会取代执行环境中的系统级组件，而且它还可以防止applet创建自己的类装载器。
　　．防止applet调用作为系统的类装载器的一部分的方法。当一个applet被执行时，浏览器调用applet类浏览器，类装载器装载所有的applet和它们相应的类。

一般地，applet不会安装新的类装载器，因此applet类装载器能一直保持对Java运行环境的控制。applet类装载器为每个applet创建一个新的名称空间，因此applet只能访问属于它自己的名称空间的类。这些类都属于标准JavaAPI库的一部分。applet不能访问属于其它applet的任何类。

●字节码验证器 　　

Java源代码在执行前需要被编译成平台独立的字节码。在一个类装载器可能允许一个指定的applet运行前，它的代码必须要由字节码验证器进行验证。事实上，Java字节码验证器假设了所有的代码都是有可能突破系统的安全措施的。
　　字节码验证器可以进行几类验证。在基本级上，它保证代码服从Java语言规范。在更复杂的级上，验证器使用一个内置的定理证明器来对代码进行验证。这可以确保applet不会伪造指针、绕过访问限制或通过非法计算来访问对象等。字节码验证器同内置在Java语言本身中的安全功能一起使用可以保证：
　　．编译后的代码格式正确 　　．内部栈将不会溢出。如果发生这样的事件，系统就会变得不稳定，此时就最容易受到黑客们的攻击。
　　．不会发生非法的数据转换如验证器将不会允许将一个整数作为指针使用。这可以保证变量不能对限制使用的内存进行访问。
　　．字节码指令将具有类型适当的参数 　　．所有的类成员访问都是合法的。也就是说，一个对象的私有数据可以保持它的隐私性。
使用字节码验证器意味着Java在允许不可信的代码在它的名称空间里运行。这样，名称空间就保证了一个applet不会影响运行环境的其它部分。代码验证保证一个applet不能溢出它的名称空间。因此到最后，JVM将只执行已经通过字节码验证的代码。

●安全管理器 　　

Java安全模型的第三个也是最重要的组件就是安全管理器。它的任务是对所有的“危险的方法”──即那些请求文件I/O、网络访问或那些想安装一个新的类装载器的类──进行验证。遇到这样的情况时，安全管理器可以对请求给予允许或否决。如，如果applet调用一个“读”方法，JVM就向安全管理器询问这个操作是否允许。如果applet是可信的，该请求就被安全管理器批准；否则即予以否决。实际上，安全管理器的作用就是保卫沙箱之间的边界。

 

       在某些情况下，这些限制是太严格了。例如，在公司的内部网中，可能希望允许某个applet访问本地文件。通过使用签名applet（signed applet），就可以针对不同情况给予其不同级别安全等级。被签名的applet携带一个可以证明其签名者身份的证书。加密技术保证这种证书不可能被伪造。如果你信任签名者，就可以给予applet额外的权限（相对沙箱给予的权限而言）。

       以下是著名的“理发师问题（Sleeping-Barber Problem）”的演示程序，我将该程序稍做修改来说明java applet安全机制的实现。

       “理发师问题（Sleeping-Barber Problem）”的描述如下：

       A barbershop consists of a waiting room with n chairs, and a barber room with one barber chair. If there are no customers to be served, the barber gose to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber.

该程序中顾客的头像图片文件保存在images目录中。默认的安全策列允许该applet读取它的代码基和任何子目录中的文件，而不是其他目录中的文件。所以当images目录在applet的代码基中时，该程序能顺利执行。

 

当images目录存放在操作系统的其他目录中时会，顾客的头像图片不能被载入，会弹出”I’m sorry I only serve local people”的消息框。

 

       为了为该applet赋予一组不同的权限和限制条件，必须：

a)         首先，使用身份认证方法来检验代码来自什么地方。

b)        然后，使用安全策列来运行代码，根据程序来源，实施你想赋予该程序的权限。

JDK配有keytool程序，该程序是一个命令行工具，用于生成和管理一组证书。

下面是Suyi如何创建一个密钥库Suyi.store并用别名Suyi生成一个密钥对的方法：

Keytool –genkey –keystore Suyi.store –alias Suyi

给该applet签名的具体操作过程如下：

       首先将类文件添加到JAR文件中：

       Jar cvf SleepingBarber.jar *.class

       然后运行jarsigner工具，并且设定JAR文件及私有密钥的别名：

       Jarsigner –keystore Suyi.store SleepingBarber.jar Suyi

       运行该applet将弹出如下提示框：

      

      

当选择“是”时，该applet将拥有全部权限，此时即使images目录不在基代码中时程序也能正常运行。选择“否”时该applet限制在沙盒中运行。

你也可以建立一个带有如下内容的策列文件applets.policy:

 

Keystore “file:Suyi.store”,”JKS”

Grant signedBy “Suyi”

{

       Permission java.io.FilePermission”<<ALL FILES>>”,”read”;

};

 

       一定要保证密钥库，策列文件和JAR文件都在同一目录中。最后要告诉applet浏览器使用该策列文件：

Appletviewer –J –Djava.security.policy=applets.policy SleepingBarber.html