1

场景：
如果我有一个包含 4 个负载的数组（a1 a2 a3 a4） 

a=[a1 a2 a3 a4] (locations of these loads must be fixed)
a=[1 2 3 3]

我想尝试将数组中的所有值增加到 3。
注意：数组a不是固定的，可以有任何值0:3

约束：

  1. 有一个不能违反的优先级数组
  2. 总增量数限制为 3

给定：

优先级数组v=[1 3 2 1]——（1 为最高优先级，3 为最低优先级）。
注意：数组v不是固定的，可以有任何值0:3

使用此优先级数组： 

a(1,1)=highest priority  
a(1,4)=2nd highest priority  
a(1,3)=3rd priority  
a(1,2)=lowest priority

实施，我的伪代码试验：

a=[1 2 3 3]
v=[1 3 2 1]
count=3

Check highest priority : a(1,1)
increment by 1
decrement count by 1
count = 2
still less than 3 ? if yes, then increment again until a(1,1)<= 3 AND count >=0
Change highest priority to 5 (so that min(v) will not pick it up)

ans : a=[3 2 3 3] ; v=[5 2 3 3] ; count = 1

Check highest priority : a(1,3)
value >= 3
Change highest priority to 5 (so that min(v) will not pick it up)
skip

ans : a=[3 2 3 3] ; v=[5 2 5 3] ; count = 1

Check highest priority : a(1,4)
value >=3 
Change highest priority to 5 (so that min(v) will not pick it up)
skip

ans : a=[3 2 3 3] ; v=[5 2 5 5] ; count = 1

Check highest priority : a(1,2)
increment by 1
decrement count by 1
count = 0
still less than 3 ? if yes, then increment again until a(1,1)<= 3 AND count >=0 
Change highest priority to 5 (so that min(v) will not pick it up)

ans = [a1 a2 a3 a4] = [3 3 3 3]

注意：如果达到优先级值 = [1 1 1 1]，则a从左到右优先（我还没有找到更好的方法）

我希望这是有道理的，并且我的伪代码显示了我正在尝试实现的内容。问我是否有不清楚的地方。

4

3 回答 3

1

你可以做这样的事情

a = [1 2 3 3]; 
v = [1 3 2 1];

% Sort a in the order of priority v
[vSrt, indSrt] = sort(v);
a = a(indSrt);

nIncsRemaining = 3; % Total no. of increments allowed
target = 3; % Target value for each value in a

for curInd = 1:length(a)
    % Difference from target
    aDiff = target - a(curInd);
    % Do we need to increment this value of a?
    if aDiff > 0
        % Increment by a maximum of nIncsRemaining
        aDelta = min(aDiff, nIncsRemaining); 
        % Increment a and decrement no. of increments remaining by the
        % same amount
        a(curInd) = a(curInd) + aDelta; 
        nIncsRemaining = nIncsRemaining - aDelta; 
    end

    % Have we done as much as we're allowed?
    if nIncsRemaining == 0, break; end
end

关键步骤是优先级数组的排序，以及通过相同索引对 a 进行排序。然后你可以循环 a，确信你从最高优先级开始。

如果您需要与输出时的输入相同的顺序，那么您可以通过执行来反转排序操作

[~, indReSrt] = sort(indSrt);
a = a(indReSrt);

数组 v 一开始没有被修改，因此您不需要反转该数组的排序。

于 2013-03-21T22:02:32.093 回答
1

另一个版本：

a = [1 2 3 3];
v = [1 3 2 1];
count = 3;
target = 3;

按优先顺序a排序v

[vSorted, order] = sort(v);
aSorted = a(order);

找到将导致count相等的位置0

pos = find(cumsum(target - aSorted) >= count);

更新所有值，直到但不包括，相应pos递减count

count = count - sum(3 - aSorted(1:pos - 1));
vSorted(1:pos - 1) = 5;
aSorted(1:pos - 1) = target;

更新值 spos

aSorted(pos) = aSorted(pos) + count;
count = 0;
if aSorted(pos) == target
    vSorted(pos) = 5;
end

恢复排序顺序

 [~, invOrder] = sort(order);
 a = aSorted(invOrder);
 v = vSorted(invOrder);

ifv仅用于确定优先级，无需更新。在所有的值都达到之后，如果count可能仍然非零，则需要对这种情况进行一些额外的处理，因为这将导致返回一个空数组。atargetpos = find(...);

于 2013-03-21T22:33:25.707 回答
1

这是我想出的：

a = [1 2 3 3];
v = [1 3 2 1];

% Get priority vector - this converts v into the indices of a that are most important in descending order. This can also be preallocated for speed or stored in place if v is not important;
priority_vec = [];
for i = 0:3
   % Get indices
   priority_vec = horzcat(priority_vec,find(v == i));   
end

% Loop over priority_vec
count = 3; % count is the number of additions you can make
for i = 1:4 % Loop over the indices of priority vec
    priority_ind = priority_vec(i); % This is the current index of most importance
    while(a(priority_ind) < 3 && count ~= 0) % Continue to add one while count is greater than 0 and the value at the priority index is less than three             
        a(priority_ind) = a(priority_ind) + 1;
        count = count - 1;
    end    
end
于 2013-03-21T22:35:22.187 回答