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;

の値を更新しますpos

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

ソート順を元に戻す

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

を優先度の決定にのみ使用する場合vは、更新する必要はありません。のすべての値が到達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 に答える