how to split a vector into small subvectors based on condition

8 views (last 30 days)
Elysi Cochin
Elysi Cochin on 15 Mar 2020
Commented: Ameer Hamza on 15 Mar 2020
how can i split a vector into smaller sub vectors, such that the sum of each vectors is less than N
N = 60
V = [30 35 24 15 14 48];
  3 Comments
Walter Roberson
Walter Roberson on 15 Mar 2020
Breaking up into individual elements satisfies the stated conditions. There are other solutions too, but the question does not prevent the algorithm from being lazy and not even trying a different solution.

Sign in to comment.

Accepted Answer

Ameer Hamza
Ameer Hamza on 15 Mar 2020
Edited: Ameer Hamza on 15 Mar 2020
From your other question: https://www.mathworks.com/matlabcentral/answers/510716-compute-from-a-set-of-parameters. I suspect that you want to find all distinct combination of elements where the sum is less than 60 while keeping the number of trips to a minimum. The following code will find an optimal solution; however, it will only work if the number of elements of V is small (say less than 20). The solution have exponential time and space complexity, so the required resources will grow very quickly. For large number of variables, I would recommend using some greedy method, which can give a sub-optimal solution.
N = 60;
V = [30 35 24 15 14 48];
a = mat2cell(repmat([0 1], numel(V), 1), ones(size(V)), 2);
combs = logical(combvec(a{:})'); % create all possible combinations
combs(1, :) = []; % remove a trivial combination
cost = sum(combs.*V, 2);
valid_index = cost < N;
valid_combs = combs(valid_index, :);
valid_costs = cost(valid_index);
[valid_costs, index] = sort(valid_costs, 'descend');
valid_combs = valid_combs(index, :);
optimal_combs = logical([]);
while ~isempty(valid_combs)
current_comb = valid_combs(1,:);
optimal_combs = [optimal_combs; current_comb];
index = any(valid_combs(:, current_comb) == valid_combs(1, current_comb), 2);
valid_combs(index, :) = [];
end
result = {};
for i=1:size(optimal_combs,1)
result{i} = V(optimal_combs(i,:));
end
  6 Comments

Sign in to comment.

More Answers (1)

Ahmed Anas
Ahmed Anas on 15 Mar 2020
Edited: Ahmed Anas on 15 Mar 2020
Dear, it will give you the desired results
clear all
clc
V = [30 35 24 15 14 48]
N=60
for i=1:size(V,2)
subsA = nchoosek(V,i);
for j=1:size(subsA)
Sum=sum(subsA(j,:));
if Sum<N
G=subsA(j,:)
end
end
end
  3 Comments
Elysi Cochin
Elysi Cochin on 15 Mar 2020
sir, i executed the code, its somewhat close,
i dont want repeatition of elements, once if i store a value into a new subvector , then i wont consider that value
my expected output is
{ [ 30 15 14] [ 35 24 ] [ 48] }

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!