第八章 装箱问题 (第10讲)

锁具装箱问题的数学模型詹国武 1 黄景文 1 周辉莉 2（1.05级化工系； 2.05级经济系）摘要：本文针对锁具如何装箱问题，建立了一个新模型，并对其进行了分析和评价。

就如何装箱问题，本文建立了一个如何对每一批锁具进行装箱和标记才能是消费者的满意度最高的模型，再具体分析实际销售情况，建立了在消费量不同情况下，如何组合已装箱好的锁具才能使满意度最大的模型以及，再对此模型进一步探讨和分析，得到一个当销售箱数超过49箱仅仅用同奇或者同偶类的锁具来组合的模型,并且对其进行了论证,最终得到最优的结果利用软件通过筛法，分别求得一批锁具钥匙的槽高由3个，4个，5个不同数组成的个数为2544，2808，528，一批锁具的个数和箱数5880和98。

再根据能够互开的锁具的条件，且根据槽高为连续的整数特性，得到结论：当一个钥匙的槽高之和为奇（偶）时，他的互开钥匙的槽高和必为偶（奇），即槽高和同为奇（偶）的必不能互开，得到把奇偶分开装箱和标记的一个初步方案，为了定量的分析不同的方案，利用概率论的方法，引入了平均互开对的概念。

对于随后的销售方案，我们利用图论知识，从最小匹配数入手，通过对平均互开对数的大小比较来衡量各个方案和组合的最优情况，得到如下结论，当销售不超过49箱时，只销售槽高和为奇（偶）的，当超过49箱时则按下问所论述的搭配方案，再进一步打破陈规，当按下文的装箱和标记，仅仅销售奇（偶），能够使抱怨的程度更小。

关键词：筛法奇偶分箱同奇或同偶销售平均对开数顾客抱怨度最小匹配一．问题的重述某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从｛1，2，3，4，5，6｝6个数中任意的取一数，但对于每个钥匙的5个槽高的取值需要满足以下两个条件1．至少有3个不同的数2．相邻的两槽的高度差不能为5满足以上两个条件的所有不同的锁具称为一批，销售部门随意的取60个装一箱出售同一批锁可以互开的条件：1.二者相对应的5个槽的高度中有4个相同2.另一个槽的高度相差为1由于销售部门随意的取60个装一箱，所以同一消费者可能买到互开的锁具，导致了消费者的不满。

贪⼼算法之装箱问题问题描述装箱问题可简述如下：设有编号为 0、1、…、n - 1 的 n 种物品，体积分别为v0、v1、…、vn-1。

将这 n 种物品装到容量都为 V 的若⼲箱⼦⾥。

约定这 n 种物品的体积均不超过 V，即对于 0≤ i＜n，有 0＜vi ≤ v。

不同的装箱⽅案所需要的箱⼦数⽬可能不同。

装箱问题要求使装尽这 n 种物品的箱⼦数要少。

贪⼼求解使⽤⼀种贪⼼策略：每次都想将当前体积最⼤的物品装⼊箱中，在这块类似于这个问题 ->>>其实在⽣活中这也是很常见的⼀种做法，在没有充⾜时间去考虑如何最优解决这类问题时直觉(第六感狗头保命)告诉我们可以这么去试试。

更直接的⼀个例⼦，⼒扣上有这么⼀道题：在柠檬⽔摊上，每⼀杯柠檬⽔的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills ⽀付的顺序）⼀次购买⼀杯。

每位顾客只买⼀杯柠檬⽔，然后向你付 5 美元、10 美元或20美元。

你必须给每个顾客正确找零，也就是说净交易是每位顾客向你⽀付 5 美元。

注意，⼀开始你⼿头没有任何零钱。

注：上⾯⿊体部分内容引⾃很明显，当客户给我们$20进⾏找零时，⾃然⽽然地就给ta找了⼀张$10加上⼀张$5，为什么这么做？⾯对$20，我们有两种⽅案可以使⽤：找三张$5给顾客找⼀张$10 以及⼀张 $5 给顾客选择第⼆种⽅案的原因对于做⽣意的⽼板应该不陌⽣，营业过程中我们需要备上⼀部分零钱在交易时⽅便找零，不⾄于出现⽆法找零的尴尬局⾯，这是商⼈们所想的，在上题中也同样适⽤。

但贪⼼算法的弊端也很明显：不考虑之前解带来的影响，仅仅为了达到当前最优解，这样”⼀根筋“的策略也不能在任何情况下得到最优解。

如只有⾯值分别为 1、5 和 11 单位的硬币，⽽希望找回总额为 15 单位的硬币。

按贪婪算法，应找 1 个 11 单位⾯值的硬币和 4 个 1 单位⾯值的硬币，共找回 5 个硬币。

但最优的解应是 3 个 5 单位⾯值的硬币。

装箱问题{2001p4--穷举法}问题描述有一个箱子容量为V(正整数，0<=V<=20000)，同时有N个物品(0<n<=30),每个物品的体积值为正整数。

要求从n个物品中，选取若干个装入箱内，使箱子的剩余空间最小。

输入：1行整数，第一个数表示箱子的容量，第二个数表示有n个物品，后面n个数分别表示这n个物品各自的体积。

输出：1个整数，表示箱子的剩余空间。

输入输出样例：输入：24 6 8 3 12 7 9 7输出：简单穷举varv,n,I,j:integer;w: array[1 .. 30] of integer; {存储N件物品的体积}a: array[0 .. 30] of integer; {存储N件物品的选取状态，1表示选取，0表示不选取} min,:Integer; {统计最小剩余量}s:integer; {累加器，统计物品体积和}beginread(v);min:=v; {初始时设定空间最小剩余量为箱子总容量}read(n);for i:=1 to n do read(w[i]);for i:=0 to n do a[i]:=0;while a[0]=0 do { a[0]作为循环控制开关}beginj:=n;while a[j]=1 do j:=j-1; {逢一进位}a[j]:=1; {设定新的状态}for i:=j+1 to n do a[i]:=0;s:=0;for i:=1 to n do s:=s+a[i]*w[i]; {计算物品的体积和}if (v-s>=0) and (v-s<min) then min:=v-s; { min存储目前的最小剩余量}end;writeln(min);end.穷举改进varv,n:integer;w: array[1 .. 30] of integer;a: array[0 .. 30] of integer;i,j,min,s,temp:Integer;beginread(v);min:=v;read(n);for i:=1 to n do read(w[i]);for i:=1 to n-1 do {排序}for j:=i+1 to n doif w[i]>w[j] thenbegintemp:=w[i]; w[i]:=w[j]; w[j]:=temp;end;for i:=0 to n do a[i]:=0;while a[0]=0 dobeginj:=n;while a[j]=1 do j:=j-1;a[j]:=1;for i:=j+1 to n do a[i]:=0;s:=0;for i:=1 to n do s:=s+a[i]*w[i];if v<s then for i:=j+1 to n do a[i]:=1 {体积总和超过容量，不再继续穷举} else if v-s<min then min:=v-s; {更正min }end;writeln(min);end.。

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期： 2011 年 07 月 16 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：摘要题目要求及有关数据我们可以把平板车装包装箱问题看成线性规划的问题进行处理，首先我们把求浪费空间最小转化为求装包装箱空间最大的问题，同时我们取每种包装箱的数量为变量，然后我们根据每一种包装箱的厚度列出每一辆车的装货时占用的空间，我们先把两辆车看成一个整体，求出两辆车占用的空间之和，然后再把这个整体分成两部分，也就是求每一辆车上所装包装箱的种类和数量。

这样我们就可以以占用两辆车的空间之和作为目标函数MAX S。

根据题意装在每一辆车上的包装箱总厚度不能超过平板车的长度；装在每一辆车上的总重量不能超过每一辆平板车的最大载重量；还有对第5、6、7类包装箱占用的空间不能超过题目中的要求；同时，装在两辆车上的同类包装箱的总件数不能超过题目给的件数，并且变量要取正整数。

在这些约束条件之下对目标函数进行求解，我们使用LINGO软件进行编程求解，最后得到装包装箱的总的最大空间为2039.9cm，即浪费的最小空间为0.1cm。

装箱问题问题描述 有⼀个箱⼦容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有⼀个体积（正整数）。

要求n个物品中，任取若⼲个装⼊箱内，使箱⼦的剩余空间为最⼩。

输⼊格式 第⼀⾏为⼀个整数，表⽰箱⼦容量； 第⼆⾏为⼀个整数，表⽰有n个物品； 接下来n⾏，每⾏⼀个整数表⽰这n个物品的各⾃体积。

输出格式 ⼀个整数，表⽰箱⼦剩余空间。

样例输⼊2468312797样例输出这题读完之后多思考思考，其实就能发现就是0-1背包问题每个物品的体积就是花费同时也是价值，也就是说这题可以转化为在总体积为v下，可以得到最⼤的价值最后⽤总体积减去最⼤的价值就是剩下最少的空间状态转移⽅程dp[j] = max(dp[j], dp[j - a[i]] + a[i]);java:import java.util.Scanner;public class Box {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int v = sc.nextInt();//箱⼦的最⼤体积int n = sc.nextInt();//物品的最⼤数量int a[] = new int[n];//存放物品的体积int dp[] = new int[v+1];//存放体积为i时的最⼤容量for (int i = 0; i < a.length; i++) {a[i] = sc.nextInt();}for (int i = 0; i < n; i++) {for (int j = v; j >= a[i]; j--) {dp[j] = Math.max(dp[j], dp[j-a[i]]+a[i]);}}System.out.println(v-dp[v]);//箱⼦容量减去⽤掉的体积}}c:#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int n;int d[20005];int a[35];int main(){int w;scanf("%d%d", &w, &n);int i, j;for (i = 0; i < n; i++){scanf("%d", &a[i]);}memset(d, 0, sizeof(d));for (i = 0; i < n; i++){for (j = w; j >= a[i]; j--)d[j] = max(d[j], d[j - a[i]] + a[i]); }printf("%d\n", w - d[w]);return 0;}。

装箱问题
装箱问题是NP问题,即在多项式时间内⽆法精确求解,⼀般采⽤近似,即启发式算法,这样可以迅速得到满意解,⽽不⼀定是最优解。

常见的算法：NF(Next Fit)近似算法，FF(First Fit)近似算法，FFD（First Fit Decreasing）近似算法，BF(best Fit),BFD(Best Fit Deceasing)等。

下次适应算法（NF）：NF算法是最简单也是最早研究的⼀个算法，它的处理⽅法是始终维持⼀个当前打开的箱⼦，对于每⼀个要装⼊的物品，检查该物品是否可以放⼊当前打开的箱⼦，如果⽆法装⼊，则打开⼀个空箱⼦，装⼊该物品，以该箱⼦作为当前的箱⼦，由于每个物品在装⼊时，只有当前打开的箱⼦和空箱可以选择，这必然造成装箱的效率低下。

⾸次适应算法(FF)：针对下次适应算法的缺陷，⾸次适应算法处理当前物品的时候，检查所有⾮空箱⼦，找到第⼀个能够放下当前物品的箱⼦并将该物品放⼊，否则则开启新的箱⼦。

最佳适应算法(BF)：与⾸次适应算法类似，唯⼀的区别时当物品装箱时，不是直接装在第⼀个可装⼊的箱⼦中，⽽是装⼊在最适合该物体的箱⼦中，如果没有该箱⼦，则开启空箱。

⾸次适应算法和最佳适应算法有⼀个缺陷，即由于物品没有实现排序，则可能由于先装⼊⼩的物品，使⼤的物品在后来放⼊时⽆法装⼊，只得开启新的箱⼦，造成了空间的浪费,因此才有了这两种算法的改进算法。

降序⾸次适应算法(FFD)：先对物品按降序排序，再按照⾸次适应算法进⾏装箱。

降序最佳适应算法(BFD)：先对物品按降序排序，再按照最佳适应算法进⾏装箱。

装箱问题算法实现讲解有一个箱子容量为V(正整数，0≤V≤20000），同时有n个物品（0≤n≤30),每个物品有一个体积（正整数）。

要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

[样例]输入：24 一个整数，表示箱子容量6 一个整数，表示有n个物品8 接下来n行，分别表示这n个物品的各自体积。

312797输出：0 一个整数，表示箱子剩余空间算法分析：本题是经典问题：0-1背包的特殊例子（加强了已知条件）。

用整形数组volume存储各件物品的体积，用布尔型函数h(i,k)表示前i个物品通过组合能否恰好装满容量k的空间，则考虑第i件物品，如果没有被选中，则问题转化为h(i-1,k);如果第i件物品被选中了，则问题转化为h(i-1,k-volume[i]),因此有如下的表达式：h(i,k)=h(i-1,k-volume[i]) || h(i-1,k);k从V开始递减，判断h(n,k)是否为真，第一个符号要求的k即为剩余空间最小时消耗的体积。

如果此时直接编写程序，就要定义一个二维数组，空间复杂度时n*v,注意到了n,v的取值范围很大，所以用二维数组存储就会有问题。

我们注意到，h(i,k)的取值仅与h(i-1,0)～h(i-1,k)有关，且如果h(i-1,k)=true,必然有h(i,k)=true,h(i,k)的值存在继承性，而程序结束时，我们也只关心h(n,k),因此，我们可以用一维数组h(k)来存储中间信息。

为了避免重复计算，可以让k从大到小变化，为了避免出现负数，k的变化范围为v～volume[i].示例程序：#include<iostream>#include<cstring>using namespace std;int v,n;int volume[31];//存储n件物品的体积int h[20001];//h[i]=1,表示n件物品通过某种组合，所构成的体积和正和等于i;//h[i]=0,表示n件物品无论如何组合，体积和都无法等于iint main(){freopen(\"in.txt\",\"r\",stdin);freopen(\"out.txt\",\"w\",stdout);int v,n,i,j,k;while(cin>>v>>n){for(i=1;i<=n;i++)cin>>volume[i];memset(h,0,sizeof(h));h[0]=1;for(i=1;i<=n;i++)for(k=v;k>=volume[i];k--)h[k]=h[k]||h[k-volume[i]];[Page]j=v;while(j>0&&h[j]==0)j--;cout<<v-j<<endl;}return 0;。

物流装箱问题数学建模
物流装箱问题是指将一批物品放置到有限的几个箱子中，使得每个箱子的利用率最高且所使用的箱子数量最少。

这是一个经典的数学优化问题，可以通过以下步骤进行建模：
1. 定义变量：假设有 n 个物品需要装箱，第 i 个物品的体积为 vi，第 j 个箱子的容积为 cj，定义决策变量 xi,j 表示将第 i 个物品放入第 j 个箱子中（取值为0或1）。

2. 约束条件：每个物品只能被放入一个箱子中，即∑j xi,j = 1，同时每个箱子的容积不能超过其限制，即∑i vi xi,j ≤ cj。

3. 目标函数：目标是最小化使用的箱子数量，因此可以定义目标函数为∑j ∑i xi,j。

4. 模型求解：该问题可以转化为混合整数线性规划问题，可以使用商业软件（如Gurobi、CPLEX等）求解，也可以使用启发式算法（如遗传算法、模拟退火等）进行求解。

需要注意的是，该问题存在多项式时间内可解的算法，但是在实际应用中，由于数据规模较大，通常需要使用近似算法或者启发式算法进行求解。

某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从{1，2，3，4，5，6}6个数（单位略）中任取一个，由于工艺及其他原因，制造锁具时对5个槽的高度有两个限定：至少有3个不同的数；相邻两槽的高度之差不能为5。

满足以上条件制造出来的所有互不相同的锁具称为一批。

从顾客的利益出发，自然希望在每批锁具中“一把钥匙开一把锁”。

但是在当前工艺条件下，对于同一批中两个锁是否能够互开，有一下实验结果：若二者相对应的5个槽的高度中有4个相同，另一个槽的高度差为1，则可能互开；在其他情形下，不可能互开。

原来，销售部门在一批锁具中随意地取60个装成一箱出售。

团体顾客往往购买几箱到几十箱，他们抱怨购买的锁具会出现互开的情形。

现聘你为顾问，回答并解决以下问题：①每一批锁具有多少个？装多少箱？②为销售部门提出一种方案，包括如何装箱（仍是60个锁具一箱），如何给箱子以标志，出售时如何利用这些标志，使团体顾客不再或减少抱怨。

③采取你提出的方案，团体顾客的购买量不超过多少箱，就可以保证一定不会出现互开的情形。

④按照原来的装箱方法，如何定量地衡量团体顾客抱怨互开的程度（试对购买一、二箱着给出具体结果）。

解：一、每批锁的把数第一问完全是一个数学问题，首先可以求出有5个槽、每个槽有6个高度的所有可能的个数为n1=65=7776，为了满足题目中提出的至少有三个不同的高度，且相邻高度差不应为5的要求，我们应该减去不满足要求的锁具。

在具体求每批锁的个数以及可以装多少箱时，既可以用排列组合法也可以编程用计算机求解。

这里我们用Matlab编程求解。

我们对5个钥匙槽的高度进行五重循环，并将判断条件设置为5个槽的高度中至少有3个不同的数且相邻两槽的高度之差不能为5，进行判断。

将满足判断条件的累加起来，最后输出即可得到一批锁具总数的大小。

可以装的箱数用锁具总数除于60即可得到。

程序如下：count=0;for h1=1:6a(1)= h1;for h2=1:6a(2)= h2;for h3=1:6a(3)= h3;for h4=1:6a(4)= h4;for h5=1:6a(5)= h5;s=0;flag=1;b=sort(a); c=diff(a);d=diff(b);for i=1:4if d(i)~=0s=s+1;endif abs(c(i))==5flag=0;endendif s>=2&flagcount=count+1;endendendendendendcountnbox=count/60程序运行结果为：count =5880nbox =98计算结果说明，每一批锁具有5880个，可以装98箱。