贪心算法实现

Question

你知道谁知道你想参加一个派对的人.假设"知道"是对称的:如果我认识你,你就认识我.你让你想每个人至少有5个新的人,以满足在党进一步的要求,而且,所以没有人感觉太孤立的,每个人都应该已经知道至少有5人在聚会.您的原始列表可能不满足这些额外的两个条件,因此您可能需要从邀请列表中删除一些人(或者您可能根本无法参与这些限制).找到您可以邀请的n个人中最大可能的子集,并满足其他两个要求.对于基本问题,找到一个O(n ^ 3)算法并解释它的顺序和逻辑.

我不是要求答案,而是要求从哪里开始.

Answer 1

听起来像是应用图算法的好地方.

形成一个人的图表,G.对于n人们来说n,图表中会有节点.链接节点i,j如果有人i知道人j.

让第一次迭代G被调用G_0.获得G_1通过使一通G,并消除谁知道太多或太少的人的任何人.(也就是说,i如果链接的数量i是< 5或者,则消除人员> n-5.)

重复上述过程,从而获得G_2,G_3直到最大的n(或左右)的迭代,从而获得G_n.此图表中剩余的人是您应邀请的人.

每个n通行证都要求n人们检查n其他人,因此算法是O(n^3).

完成此任务的MATLAB代码(你没有要求它,但我认为它很有趣并且无论如何都写了它):

% number of people on original list
N = 10

% number of connections to (attempt) to generate
% may include self-links (i,i) or duplicates
M = 40

% threshold for "too few" friends
p = 3

% threshold for "too many" friends
q = 3

% Generate connections at random
G = zeros(N);
for k = 1:M
    i = randi(N);
    j = randi(N);
    G(i,j) = 1;
    G(j,i) = 1;
end

% define people to not be their own friends
for i = 1:N
    G(i,i) = 0;
end

% make a copy for future comparison to final G
G_orig = G

% '1' means invited, '0' means not invited
invited = ones(1,N);

% make N passes over graph
for k = 1:N
    % number of people still on the candidate list
    n = sum(invited); 
    % inspect the i'th person
    for i = 1:N 
        people_known = sum(G(i,:));
        if invited(i) == 1 && ((people_known < p) || (people_known > n-q))
            fprintf('Person %i was eliminated. (He knew %i of the %i invitees.)\n',i,people_known,n);
            invited(i) = 0;
            G(i,:) = zeros(1,N);
            G(:,i) = zeros(1,N);
        end
    end
end

fprintf('\n\nFinal connection graph')
G

disp 'People to invite:'
invited

disp 'Total invitees:'
n

样本输出(10人,40个连接,必须至少知道3个人,一定不能知道至少3个人)

G_orig =

     0     0     1     1     0     0     0     0     1     0
     0     0     0     0     0     1     0     0     0     1
     1     0     0     1     1     1     0     0     0     1
     1     0     1     0     0     1     0     1     1     0
     0     0     1     0     0     0     1     0     1     1
     0     1     1     1     0     0     0     1     0     1
     0     0     0     0     1     0     0     0     1     0
     0     0     0     1     0     1     0     0     0     1
     1     0     0     1     1     0     1     0     0     1
     0     1     1     0     1     1     0     1     1     0

Person 2 was eliminated. (He knew 2 of the 10 invitees.)
Person 7 was eliminated. (He knew 2 of the 10 invitees.)


Final connection graph
G =

     0     0     1     1     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     0     0
     1     0     0     1     1     1     0     0     0     1
     1     0     1     0     0     1     0     1     1     0
     0     0     1     0     0     0     0     0     1     1
     0     0     1     1     0     0     0     1     0     1
     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     0     1     0     0     0     1
     1     0     0     1     1     0     0     0     0     1
     0     0     1     0     1     1     0     1     1     0

People to invite:

invited =

     1     0     1     1     1     1     0     1     1     1

Total invitees:

n =

     8

Answer 2

我假设以下数据结构用于表示信息：

Person
    name : string, if this is empty or null, the person isnt not invited to party
    knows: array of pointers to type Person. Indicates whom this person 'knows'
    knows_cnt : size of "knows" array

每个人（包括主持人）的详细信息可以存储在“Person individual[n]”中。

聚会的主持人处于第一位置。

我可能需要的算法子程序：

RemovePerson (individuals, n, i)
// removes i'th person from individuals an array of n persons

    set individuals[i].name to empty so that this person is discarded

    For j from 1 to individuals[i].knows_cnt
    // as knows is symmetric, we can get the persons' contact right away
        Person contact = individuals[i].knows[j]

        if contact.name is empty, 
            continue

        modify contact.knows to remove i'th person. 
        modify corresponding contact.knows_cnt
    end for

end RemovePerson

提出的算法：

change = true 
invitees = n

while [change == true]
    change = false

    for i = 2 to n do
    // start from 2 to prevent the host getting discarded due to condition #2

        if individuals[i].name is empty, 
            continue

        // condition #1,
        // check if the person knows atleast 5 people
        if individuals[i].knows_cnt < 5
            change = true 
            invitees = invitees  - 1
            RemovePerson(individuals, n, i)

        // condition #2
        // check to find out if the person will get to know 5 new people
        if (invitees - individuals[i].knows_cnt) < 5
            change = true 
            invitees = invitees  - 1
            RemovePerson(individuals, n, i)

    end for

end while   

return invitees

如果您在理解该算法时遇到任何困难，请告诉我。