|
|
发表于 2012-6-26 12:57:00
|
显示全部楼层
Re:自己给自己出了一道题却解不开，求大神帮忙！
一、如果钥匙包和三个箱子是不可重复的。
当拿到三个钥匙包的时候，各种钥匙的数目是确定的了，分别为k=（k1，k2，k3）；
当遇到了三个箱子的时候，各个箱子需要各种钥匙的数目也是固定的了，可以用一个矩阵来表示：
B=[n11 n12 n13
n21 n22 n23
n31 n32 n33]
其中每一行对应一个箱子需要各种钥匙的数目。
那么问题就转化成一个整数优化的问题：
设开启各个箱子的数目分别为 x=（x1，x2，x3）
目标函数为：
min Z=sum（x）
约束条件为：
xB<=k 且 x为自然数
求解整数规划一般用分支定界法，但是由于三个钥匙包中的钥匙至少可以开启0个箱子，最多开启3个箱子，完全可以用枚举的方法来求解（每个箱子的个数从0到3循环）。
另外：获得钥匙包的情况总共有C（6,3）=20种；遇到箱子的情况总共有C（6,3）=20种；而且
钥匙包和箱子包（三个算一个包）的对应情况有20×20=400种，用程序枚举也很快。
根据以上的思路，用matlab求解之。
子函数一，用于求获得各种钥匙和的情况集合
function KeySum=KeyNum(Key,k)
% k个钥匙宝所含各种钥匙和的情况
KeyIndex=combntns(1:size(Key,1),k);
n=size(KeyIndex,1);
KeySum=zeros(n,size(Key,2));
for i=1:n
KeySum(i, =sum(Key(KeyIndex(i,:),:));
end
子函数二，用于求遇到箱子的情况集合
function BoxSum=BoxNum(Box,k)
% 遇到k个箱子需要钥匙的所有情况
BoxIndex=combntns(1:size(Box,1),k);
n=size(BoxIndex,1);
BoxSum=zeros(k,size(Box,2),n);
for i=1:n
BoxSum(:,:,i)=Box(BoxIndex(i,:),:);
end
子函数三，枚举法求整数规划的最优解
function [Box,MaxBoxNum]=MaxBox(K,B)
% 简单的循环求开启箱子的最大个数
MaxBoxNum=0;
Box=[0 0 0];
for box_1=0:3
for box_2=0:3
for box_3=0:3
KeyNeed=B'*[box_1 box_2 box_3]';
BoxNum=box_1+box_2+box_3;
if KeyNeed(1)<=K(1) && KeyNeed(2)<=K(2) && KeyNeed(3)<=K(3)
if BoxNum>MaxBoxNum
MaxBoxNum=BoxNum;
Box=[box_1,box_2,box_3];
end
end
end
end
end
主函数：
clc;clear all;format long g;
Key=[1 1 0
1 0 1
0 1 1
2 0 0
0 2 0
0 0 2];
Box=[1 1 0
1 0 1
0 1 1
2 0 0
0 2 0
0 0 2];
K=KeyNum(Key,3);
B=BoxNum(Box,3);
S=0;
for k=1:20
for b=1:20
[~,MaxBoxNum]=MaxBox(K(k,:),B(:,:,b));
S=S+MaxBoxNum;
end
end
fprintf('平均可以开启 %g 个箱子。\n',S/400);
运行结果：
平均可以开启 2.19 个箱子。
开启箱子数目及对应的概率为：
0 1 2 3
3/400 63/400 189/400 29/80
二、如果钥匙包和三个箱子是可以重复的。
思路和上面相似，只不过求钥匙包情况集合以及三个箱子情况集合的方法稍有不同，但是也比较简单。虽然，由于可以重复，获得钥匙的数目情况与上面的情况不同，但是可以开启的箱子个数仍然是从0到3，即便如此为了保险起见，将搜索范围扩大到从0到6（经验证，两种搜索范围的结果是相同的）。下面仅罗列结果：
子函数一：
function CombIndex=Comb3(N)
% 从1:N中可重复得选择3个数的所有情况组合
CoIn_1=combntns(1:N,3);
CoIn_2=combntns(1:N,2);
CoIn_3=combntns(1:N,1);
CombIndex=[CoIn_1;[CoIn_2 CoIn_2(:,1)];[CoIn_2 CoIn_2(:,2)];[CoIn_3 CoIn_3 CoIn_3]];
子函数二：
function KeySum=KeyNum(Key)
KeyIndex=Comb3(size(Key,1));
n=size(KeyIndex,1);
KeySum=zeros(n,size(Key,2));
for i=1:n
KeySum(i,:)=sum(Key(KeyIndex(i,:),:));
end
子函数三：
function BoxSum=BoxNum(Box)
BoxIndex=Comb3(size(Box,1));
n=size(BoxIndex,1);
BoxSum=zeros(3,size(Box,2),n);
for i=1:n
BoxSum(:,:,i)=Box(BoxIndex(i,:),:);
end
子函数四：
function [Box,MaxBoxNum]=MaxBox(K,B)
% 简单的循环求开启箱子的最大个数
MaxBoxNum=0;
Box=[0 0 0];
for box_1=0:6
for box_2=0:6
for box_3=0:6
KeyNeed=B'*[box_1 box_2 box_3]';
BoxNum=box_1+box_2+box_3;
if KeyNeed(1)<=K(1) && KeyNeed(2)<=K(2) && KeyNeed(3)<=K(3)
if BoxNum>MaxBoxNum
MaxBoxNum=BoxNum;
Box=[box_1,box_2,box_3];
end
end
end
end
end
主函数：
clc;clear all;format long g;
Key=[1 1 0
1 0 1
0 1 1
2 0 0
0 2 0
0 0 2];
Box=[1 1 0
1 0 1
0 1 1
2 0 0
0 2 0
0 0 2];
K=KeyNum(Key);
B=BoxNum(Box);
j=1;S=zeros(1,size(K,1)*size(B,3));
for k=1:size(K,1)
for b=1:size(B,3)
[~,MaxBoxNum]=MaxBox(K(k,:),B(:,:,b));
S(j)=MaxBoxNum;
j=j+1;
end
end
fprintf('平均可以开启 %g 个箱子。\n',mean(S));
运行结果：
平均可以开启 1.65689 个箱子。
对应开启箱子个数的概率为：
0 1 2 3
64/449 166/631 95/244 57/278 |
|
