How to iterate through all combinations within a FOR loop?
61 ビュー (過去 30 日間)
古いコメントを表示
Hi,
I want to set up a loop where items in one array is subtracted from from elements in another array while minimising the leftovers.
A simplified example
Six rolls of three different lengths (10, 12, 15) are in one array roll_list. The first row is the lengths and the second row is the corresponding quantities.
Ten different parts of lengths (7, 6, 6, 5, 4, 7, 5, 4, 6, 5) need to be made from the six available rolls.
The parts need to be produced in the order as shown in the array part_list, but the rolls may be used in any order.
How can I set up a loop to iterate all the possible combination and find out the least amount of waste? I have managed to do one possible iteration sequential to the roll_list array, but I am struggling to figure out how to attempt all possible combinations.
Appreciate any suggestions.
----EDIT ----
- One part cannot be made using more than one roll. So Part A cannot include material from Roll X and Y.
- Once a roll enters production, it needs to be used straight away. It cannot be removed from production and brought back to be reused.
roll_list = [10 12 15; 3 1 2];
roll_tot=sum(roll_list(1,:).*roll_list(2,:));
part_list = [7 6 6 5 4 7 5 4 6 5];
parts_total_length = sum(part_list);
b=1;
c=1;
waste=0;
for a = 1:length(part_list)
if roll_list(1,b) >= part_list(a) && roll_list(2,c) >= 1
roll_list(1,b) = roll_list(1,b) - part_list(a);
else
waste = waste + roll_list(1,b);
roll_list(2,c) = roll_list(2,c)-1;
roll_list(1,:) = [10 12 15];
if roll_list(2,c) == 0
b=b+1;
c=c+1;
end
roll_list(1,b) = roll_list(1,b) - part_list(a);
end
end
16 件のコメント
Matt J
2022 年 1 月 6 日
The actual problem involves tens of roll lengths, hundreds of quantities, and thousands of parts.
I don't think you're going to be able to handle thousands of parts. The number of combinations grows exponentially with the number of parts, something like,
N=size(roll_list,2);
M=numel(part_list);
numberofCombinations=N.^M
So, if M is in the 1000s, I don't think there's any hope. As a compromise, you can decompose the parts list into sub-lists and optimize over each one sequentially.
採用された回答
Matt J
2022 年 1 月 6 日
編集済み: Matt J
2022 年 1 月 6 日
Here's a dynamic programming approach:
roll_list = [10 12 15; 3 1 2];
part_list = [7 6 6 5 4 7 5 4 6 5];
roll_list=sortrows(roll_list.',1).'; %ensure sorted
[minwaste,schedule]=optimizeIt(roll_list(1,:),roll_list(2,:), part_list)
function [minwaste,schedule]=optimizeIt(lengths,quantities, part_list)
roll_tot=sum(lengths.*quantities);
parts_total_length = sum(part_list);
if roll_tot<parts_total_length %problem is infeasible, bail out
minwaste=Inf; schedule=[]; return
end
n=find(lengths>=part_list(1) ,1 );
if isempty(n) %problem is infeasible, bail out
minwaste=Inf; schedule=[]; return
end
M=numel(part_list);
N=numel(lengths);
C=cumsum(part_list);
Wastes=inf(N,1);
Schedules=cell(N,1);
for i=n:N
L=lengths(i); %pick a length
j=find(L>=C,1,'last');
if j==M % L covers all remaining parts
% No need to consider longer rolls
Wastes(i)=L-C(end);
break
else
plist=part_list(j+1:end);
[llist,qlist]=deal(lengths,quantities);
if quantities(i)==1 %shrink lists
llist(i)=[];
qlist(i)=[];
else
qlist(i)=quantities(i)-1;
end
if isempty(qlist) && ~isempty(plist)
continue
end
Wastes(i)= (L-C(j));
[cost_to_go,Schedules{i}]=optimizeIt(llist,qlist, plist); %RECURSE!!!
Wastes(i)=Wastes(i)+cost_to_go;
end
end
[minwaste,imin]=min(Wastes);
schedule=[lengths(imin),Schedules{imin}];
end
その他の回答 (0 件)
参考
カテゴリ
Help Center および File Exchange で Matrices and Arrays についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!