主页 / 问题 / 1538768
Accepted
Clark Devlin
Asked:2023-09-02 17:00:15 +0000 UTC2023-09-02 17:00:15 +0000 UTC

如何加速暴力算法？（纸杯蛋糕问题）

  • 772

有问题，可以用python或者使用pluses来解决，照片条件： 在此输入图像描述

文本条件：

你的朋友尤利娅准备了美味的纸杯蛋糕。它们每个都有三个参数 - 口味、浇头量、奶油量，i 纸杯蛋糕有风味 ti、浇头量 di 和 ci 顶部奶油。Julia 不使用公制，因此这些数字可以为零或负数。为了绕一圈，她需要拿恰好 m 个纸杯蛋糕。令该集合的质量为总口味模+总洒水量模+总奶油量模。换句话说，如果选择纸杯蛋糕 i1....im，则该集合的质量为模数(ti1+ti2+tim) + 模数(di1+di2+dim) + 模数(ci1+ci2+cim) 一个蛋糕每种类型的纸杯蛋糕最多只能吃一次。在第一行中，输入准备的金额和要服用的金额。在剩下的行中，输入口味、奶油量、

我编写了一个算法，该算法在已知测试中可以正常工作，但在其他测试中需要时间，我怎样才能加快速度？

def max_quality(n, m, cupcakes):
    max_quality = 0
    for i in range(1 << n):
        if bin(i).count('1') == m:
            taste_sum = 0
            frosting_sum = 0
            sprinkle_sum = 0
            for j in range(n):
                if i & (1 << j):
                    ti, ci, di = cupcakes[j]
                    taste_sum += ti
                    frosting_sum += ci
                    sprinkle_sum += di
            quality = abs(taste_sum) + abs(frosting_sum) + abs(sprinkle_sum)
            max_quality = max(max_quality, quality)
    return max_quality
 
n, m = map(int, input().split())
cupcakes = [list(map(int, input().split())) for _ in range(n)]
result = max_quality(n, m, cupcakes)
print(result)

测试示例和答案：

5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15

ответ - 54

10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

Ответ 638
python

4 个回答

  1. 好吧，既然TS自己做出了决定并且不再是秘密，我认为没有理由进一步隐藏它......

    Stanislav Volodarskiy 这个名字的解决方案（在他的隐藏答案中） - https://bit.ly/3R5kJ6Q

    #include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char * argv[])
{
    int n, m;
    long long best = 0;
    cin >> n >> m;
    vector<long long> t[8];
    for(int i = 0; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        t[0].push_back( a + b + c);
        t[1].push_back( a + b - c);
        t[2].push_back( a - b + c);
        t[3].push_back( a - b - c);
        t[4].push_back(-a + b + c);
        t[5].push_back(-a + b - c);
        t[6].push_back(-a - b + c);
        t[7].push_back(-a - b - c);
    }
    for(int i = 0; i < 8; ++i)
    {
        sort(t[i].begin(),t[i].end(),greater<long long>());
        long long s = 0;
        for(int j = 0; j < m; ++j) s += t[i][j];
        if (best < s) best = s;
    }
    cout << best;
}
    • 4
  2. Best Answer

    最终的表达式具有三个模块。它们可以被删除，从而产生八种字符组合。每个组合都是线性的。选择最大数量的m个纸杯蛋糕就足够了（当然要考虑到标志）。在八个金额中，您需要取最大值。

    import heapq
import itertools


n, m = map(int, input().split())
capcakes = [tuple(map(int, input().split())) for _ in range(n)]
print(max(
    sum(heapq.nlargest(
        m,
        (sum(k(v) for k, v in zip(keys, c)) for c in capcakes)
    ))
    for keys in itertools.product((lambda x: x, lambda x: -x), repeat=3)
))

    解决方案的复杂度为 O(nlogm)。

    需要heapq.nlargest来为nlog mm选择最美味的蛋糕。排序将在nlog n中执行相同的操作。在实践中，不会有时间增益：Python 中的排序非常快（一个好的常量），但堆很慢（一个坏的常量）。速度增益取决于logn和logm的比率。并且m ≤ n ≤ 1000。对数之比约为十。排序会赢。所以——为艺术而艺术。heapq.nlargest

    在 C++ 中，有std::nth_element。有了它的帮助，你可以摆脱对数（好吧，几乎）。平均复杂度为O(n) ，最坏情况为O(nlogm) ：

    #include <algorithm>
#include <array>
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int m;
    std::cin >> m;
    std::vector<std::array<int64_t, 3>> capcakes(n);
    for (auto &c : capcakes) {
        std::cin >> c[0] >> c[1] >> c[2];
    }
    int64_t max_taste = 0;
    for (auto s0 : {-1, 1}) {
        for (auto s1 : {-1, 1}) {
            for (auto s2 : {-1, 1}) {
                std::vector<int64_t> tastes;
                for (auto &c : capcakes) {
                    tastes.push_back(s0 * c[0] + s1 * c[1] + s2 * c[2]);
                }
                std::nth_element(
                    tastes.begin(),
                    tastes.end() - m,
                    tastes.end()
                );
                max_taste = std::max(
                    max_taste,
                    std::accumulate(
                        tastes.end() - m,
                        tastes.end(),
                        static_cast<int64_t>(0)
                    )
                );
            }
        }
    }
    std::cout << max_taste << '\n';
}
    • 3

  3. 这不是最优雅的解决方案，可以减少功能中的所有内容，但不再有力量了。简要说明：

    让我们知道，在某些值下可以达到最大值。在这种情况下，我们知道 t_i、d_i 和 c_i 之和的符号。不失一般性，我们假设它们都是“+”。那么实际上最大值与相同总和的最大值一致，但没有模块。在这种情况下，我们最大化 t_i + d_i + c_i 值的总和。这样，我们就解决了“n个数据中m个最大值之和是多少”这样的问题。

    总共需要对每个表达式±t_i±d_i±c_i找到该值最大的m个值，并将它们相加。你得到8个数字。其中我们取最大值。

    复杂度 – n log(m)。

    PS我确实为自己解决了这个问题，而不是为了竞赛，规则中没有任何地方说我不能监视/复制/谷歌/等等。

    #define loong long long
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
  cin.sync_with_stdio(false);
 
  loong n, m;
  cin >> n >> m;
 
  vector<loong> t(n), d(n), c(n);
  for (loong i = 0; i < n; ++i) {
    cin >> t[i] >> d[i] >> c[i];
  }
 
  loong l = 0;
  // + + +
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = + t[i] + d[i] + c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = sum;
  }
 
  // + + -
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = + t[i] + d[i] - c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  // + - +
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = + t[i] - d[i] + c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  // + - -
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = + t[i] - d[i] - c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  // - + +
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = - t[i] + d[i] + c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  // - + -
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = - t[i] + d[i] - c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  // - - +
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = - t[i] - d[i] + c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  // - - -
  {
    vector<loong> a(n);
    for (loong i = 0; i < n; ++i) {
      a[i] = - t[i] - d[i] - c[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    loong sum = 0;
    for (loong i = 0; i < m; ++i) {
      sum += a[i];
    }
    l = max(l, sum);
  }
 
  cout << l << endl;
 
  return 0;
}
    • 3

  4. 既然有这样的酒发生，这是我的解决方案：

    from functools import reduce

def ps(cs):
    ts, cs, ds = reduce(lambda v, o: (v[0] + o[0], v[1] + o[1], v[2] + o[2])
        , sorted(ck, key = lambda o: (o[0] if cs & 1 else -o[0])
                 + (o[1] if cs & 2 else -o[1])
                 + (o[2] if cs & 4 else -o[2]), reverse = True)[:m])
    return abs(ts) + abs(cs) + abs(ds)
        
n, m = map(int, input().split())
ck = [list(map(int, input().split())) for _ in range(n)]
print(max(ps(i) for i in range(8)))

    问题的作者在他的解决方案中描述了该算法。

    以前的

    我想了很久，没有找到一个既不过度，又不过度的方法。有各种各样的假设，但都无法被证明（更快地找到了反例:-)）。

    因此，我提出了一种暴力解决方案，但需要积累数量来进行优化。

    def ps(i, ti, ci, di, cupcakes, m):
    mq = -1
    m -= 1
    hj = len(cupcakes) - m + 1
    for j in range(i + 1, hj):
        tj, cj, dj = cupcakes[j]
        tj, cj, dj = ti + tj, ci + cj, di + dj
        if m > 1:
            tj, cj, dj = ps(j, tj, cj, dj, cupcakes, m)
        if (q := abs(tj) + abs(cj) + abs(dj)) > mq:
            mq, tm, cm, dm = q, tj, cj, dj
    return tm, cm, dm
        
n, m = map(int, input().split())
ti, ci, di = ps(-1, 0, 0, 0, [list(map(int, input().split())) for _ in range(n)], m + 1)
print(abs(ti) + abs(ci) + abs(di))

    使用了递归。堆栈足以满足最大值m=1000。

    • 2

相关问题