function [B,ans]=SimplexCG(filename)
file = [.\gcut\',filename,'.txt']; %//算例存放在下级gcut文件夹中
data = textread(file);
m=data(1,1);
W=data(2,1);
H=data(2,2);
w=data(3:2+m,1)';
h=data(3:2+m,2)';
d=data(3:2+m,3)';
x=d;
B=eye(m);
P=DPP(W,w);
Q=DPP(H,h);
r=length(P);
s=length(Q);
m_V=zeros(m,r,s);
m_item=zeros(m,r,s,m);
m_guil=zeros(m,r,s);
m_pos=zeros(m,r,s);
while(true)
y=ones(1,m)/B;
[z,V,item,guillotine,position]=DP(W,H,w,h,y);
if y*z<=1
break;
end
omega=inv(B)*z;
t=1e6;
s=-1;
for j=1:m
if omega(j)<=0
continue;
end
if t>(x(j)/omega(j))
t=x(j)/omega(j);
s=j;
end
end
if s==-1
break;
end
m_V(s,:,:)=V;
m_item(s,:,:,:)=item;
m_guil(s,:,:)=guillotine;
m_pos(s,:,:)=position;
for i=1:m
B(i,s)=z(i);
if i==s
x(i)=t;
else
x(i)=x(i)-omega(i)*t;
end
end
end
ans = x;
P=DPP(W,w);
Q=DPP(H,h);
r=length(P);
s=length(Q);
%//画出最后方案
for i=1:m
figure(i);
hold on
plot([0,W,W],[H,H,0])
cut(1).w=r;
cut(1).h=s;
cut(1).x=0;
cut(1).y=0;
while(~isempty(cut))
a=cut(1).w;
b=cut(1).h;
x=cut(1).x;
y=cut(1).y;
cut(1)=[];
num=length(cut);
if m_guil(i,a,b)==0
continue;
end
if m_guil(i,a,b)==1
plot([x+m_pos(i,a,b),x+m_pos(i,a,b)],[y,y+Q(b)]);
[~,cut(num+1).w]=max(P(P<=m_pos(i,a,b)));
cut(num+1).h=b;
cut(num+1).x=x;
cut(num+1).y=y;
[~,cut(num+2).w]=max(P(P<=P(a)-m_pos(i,a,b)));
cut(num+2).h=b;
cut(num+2).x=x+m_pos(i,a,b);
cut(num+2).y=y;
end
if m_guil(i,a,b)==2
plot([x,x+P(a)],[y+m_pos(i,a,b),y+m_pos(i,a,b)]);
cut(num+1).w=a;
[~,cut(num+1).h]=max(Q(Q<=m_pos(i,a,b)));
cut(num+1).x=x;
cut(num+1).y=y;
cut(num+2).w=a;
[~,cut(num+2).h]=max(Q(Q<=Q(b)-m_pos(i,a,b)));
cut(num+2).x=x;
cut(num+2).y=y+m_pos(i,a,b);
end
end
end
下面三段是主程序运行需要的其他函数
function P=DPP(D,d)
P=0;
m = length(d);
for j=0:D
c(j+1)=0;
end
for i=1:m
for j=d(i):D
if c(j+1)1)+d(i)
c(j+1)=c(j-d(i)+1)+d(i);
end
end
end
mind = min(d);
for j=1:D-mind
if c(j+1)==j
P=[P,j];
end
end
P=[P,D];
function [z,V,item,guillotine,position]=DP(W,H,w,h,v)
m=length(w);
P=DPP(W,w);
Q=DPP(H,h);
r=length(P);
s=length(Q);
V=zeros(r,s);
item=zeros(r,s,m);
guillotine=zeros(r,s);
position=zeros(r,s);
for i=1:r
for j=1:s
[V(i,j),item(i,j,:)]=inital_dp(w,h,v,P,Q,i,j);
guillotine(i,j)=0;
end
end
for i=2:r
for j=2:s
[~,n]=max(P(P<=floor(P(i)/2)));
for x=1:n
[~,t]=max(P(P<=(P(i)-P(x))));
if V(i,j)<V(x,j)+V(t,j)
V(i,j)=V(x,j)+V(t,j);
item(i,j,:)=item(x,j,:)+item(t,j,:);
position(i,j)=P(x);
guillotine(i,j)=1; %w方向切割
end
end
[~,n]=max(Q(Q<=floor(Q(j)/2)));
for y=1:n
[~,t]=max(Q(Q<=(Q(j)-Q(y))));
if V(i,j)<V(i,y)+V(i,t)
V(i,j)=V(i,y)+V(i,t);
item(i,j,:)=item(i,y,:)+item(i,t,:);
position(i,j)=Q(y);
guillotine(i,j)=2; %h方向切割
end
end
end
end
z=zeros(m,1);
for i=1:m
z(i)=item(r,s,i);
end
function [V,maxk]=inital_dp(w,h,v,P,Q,i,j)
V=0;
m=length(v);
maxk=zeros(1,m);
for k=1:m
if w(k)>P(i)
continue;
end
if h(k)>Q(j)
continue;
end
if v(k)>V
V=v(k);
maxk=zeros(1,m);
maxk(k)=1;
end
end