问题描述
对于某一n变量的0-1规划问题,其可能的解集有2^n中组合。如n=3,显然组合情况为:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
在一定的情况下,需要枚举所有可能的组合。如何编程构造以上组合数呢?
问题要点
此问题解决的要点在于二进制转换,如以上组合中的 0 0 0
若看做二进制数则对应于0 = 2^0 -1
,而 1 1 1
若看做二进制数则对应于7 = 2^3 -1
,即以上每一个组合数,均与一个二进制数值对应。
利用此原理,可以构造出所有的组合数。
程序实现
clc,clear
k = 4; % 组合阶数
n = 2^k; % 组合数量
index = 0:n-1; % 组合序号
index = index'; % 转置
nBin = dec2bin(index); % 十进制转换二进制
combination = zeros(k,n);
for iloop = 1:n
temp = nBin(iloop,:)';
tempCol = str2num(temp); % 二进制文本转换01 序列
combination(:,iloop) = tempCol;
end
以k =4测试程序,结果如下:
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1