algorithm - 有竞争力的编程 - 用 P、Q 和 R 配料准备完美的 curry

Question

最近我接到了一个我无法完成的竞争性编程任务。只是想知道问题的最佳解决方案

“A”是 N 个整数的零索引数组。A 的元素是 [−99,999,999 到 99,999,999] 范围内的整数

'curry' 是由 N 个字符组成的字符串，每个字符都是 'P'、'Q' 或 'R'，并且数组对应的索引就是每种食材的重量。

如果“P”、“Q”和“R”的总重量之和相等，则 curry 是完美的。

写一个函数

makeCurry(Array)

这样，给定一个由 N 个整数组成的零索引数组 Array，返回该数组的完美 curry。

如果该数组不存在完美 curry ，该函数应返回字符串“noLuck”。

例如，给定数组 Array 这样

A[0] = 3 A[1] = 7 A[2] = 2 A[3] = 5 A[4] = 4

函数可能会返回“PQRRP”，如上所述。给定数组 A 使得

A[0] = 3 A[1] = 6 A[2] = 9

该函数应返回“noLuck”。

我试过的方法是这样的

import collections

class GetPerfectCurry(object):
    def __init__(self):
        self.curry = ''
        self.curry_stats = collections.Counter({'P': 0, 'Q': 0, 'R': 0})
        pass

    def get_perfect_curry(self, A):
        if len(A) == 0:
            return "noLuck"
        A.sort(reverse=True)
        for i, ele in enumerate(A):
            self.check_which_key_to_add_new_element_and_add_element(ele)
        if self.curry_stats['P'] == self.curry_stats['Q'] == self.curry_stats['R']:
            return self.curry
        else:
            return "noLuck"

    def check_which_key_to_add_new_element_and_add_element(self, val):
        # get the maximum current value
        # check if addition of new value with any of the other two key equals the max value
        # if yes then add that value and append the key in the curry string
        current_max_key = max(self.curry_stats, key=self.curry_stats.get)
        check_for_equality = False
        key_to_append = None
        for key, ele in enumerate(self.curry_stats):
            if ele != current_max_key:
                if self.curry_stats[ele] + val == self.curry_stats[current_max_key]:
                    check_for_equality = True
                    key_to_append = ele
        if check_for_equality:
            self.curry_stats.update(str(key_to_append) * val)
            self.curry += str(key_to_append)
            pass
        else:
            # if no value addition equals the current max
            # then find the current lowest value and add it to that key
            current_lowest_key = min(self.curry_stats, key=self.curry_stats.get)
            self.curry_stats.update(str(current_lowest_key)*val)
            self.curry += str(current_lowest_key)


if __name__ == '__main__':
    perfect_curry = GetPerfectCurry()
    A = [3, 7, 2, 5, 4]
    # A = [3, 6, 9]
    # A = [2, 9, 6, 3, 7]
    res = perfect_curry.get_perfect_curry(A)
    print(res)

但这是不正确的。在过去的四个小时里为这个问题的最佳解决方案而绞尽脑汁

Answer 1

一种可能的算法如下:

• 对权重求和。如果它不是 3 的倍数，那就不走运。如果是，除以 3 得到目标。

• 找到 A 的总和为目标的子集。对于此类子集，将其删除并得到 B。找到 B 的一个子集加起来达到目标​​。

这是一个 Java 实现(我不是 Python 专家，抱歉):

import java.util.Arrays;

public class Main
{
    // Test if selected elements add up to target
    static boolean check(int[] a, int selection, int target)
    {
        int sum = 0;
        for(int i=0;i<a.length;i++)
        {
            if(((selection>>i) & 1) == 1)
                sum += a[i];
        }
        return sum==target;
    }

    // Remove the selected elements
    static int[] exclude(int[] a, int selection)
    {
        int[] res = new int[a.length];
        int j = 0;
        for(int i=0;i<a.length;i++)
        {
            if(((selection>>i) & 1) == 0)
                res[j++] = a[i];
        }
        return Arrays.copyOf(res, j);
    }

    static String getCurry(int[] a)
    {
        int sum = 0;
        for(int x : a)
            sum += x;
        if(sum%3 > 0)
            return "noLuck";
        int target = sum/3;
        int max1 = 1<<a.length; // 2^length
        for(int i=0;i<max1;i++)
        {
            if(check(a, i, target))
            {
                int[] b = exclude(a, i);
                int max2 = 1<<b.length; // 2^length
                for(int j=0;j<max2;j++)
                {
                    if(check(b, j, target))
                        return formatSolution(i, j, a.length);
                }
            }
        }
        return "noLuck";
    }

    static String formatSolution(int p, int q, int len)
    {
        char[] res = new char[len];
        Arrays.fill(res, 'R');
        int j = 0;
        for(int i=0;i<len;i++)
        {
            if(((p>>i) & 1) == 1)
                res[i] = 'P';
            else
            {
                if(((q>>j) & 1) == 1)
                    res[i] = 'Q';
                j++;
            }
        }
        return new String(res);
    }

    public static void main(String[] args)
    {
//      int[] a = new int[]{3, 7, 2, 5, 4};
//      int[] a = new int[]{1, 1, 2, -1};
        int[] a = new int[]{5, 4, 3, 3, 3, 3, 3, 3};
        System.out.println(getCurry(a));
    }
}

可以测试一下here .