3

这个问题来自编程比赛，我无法在可接受的时间内解决它。

你得到一个整数数组a。找到不超过给定整数的恰好元素（不一定是连续的）n的最大总和。skm (s < m)

约束：

 0 < k <= n < 100
 m < 3000
 0 < a[i] < 100

信息：对于给定的输入，保证存在解决方案。

现在，我想我最好的选择是 DP 方法，但无法提出正确的公式。

4

4 回答 4

2

两种公认的方法都较差。此外，这不是DP可以解决的问题类型。

以下是通过示例说明的正确方法：

想象 a = { 2, 3, 5, 9, 11, 14, 17, 23 }（因此 n = 8），k = 3 和 s = 30

对数组 a 排序。

在数组中定义三个从 1 到 n 的指针 P1、P2 和 P3。P1 < P2 < P3

将 P3 设置为 a_max（此处为 23），将 P1 设置为 1，将 P2 设置为 2。计算总和 s（此处为 23 + 2 + 3 = 28）。如果 s > S，则将 P3 减一并重试，直到找到解决方案。如果 P3 < 3，则无解。将您的第一个解决方案存储为迄今为止最知名的解决方案 (BKSSF)。

接下来，增加 P2 直到 s > S。如果找到更好的解决方案，请更新 BKSSF。将 P2 减一。

接下来增加 P1 直到 s > S。如果找到更好的解决方案，请更新。

现在回到 P2 并将其减一。

然后增加 P1 直到 s > S. 等等。

你可以看到这是一个递归算法，其中每增加或减少，就会有一个或多个相应的减少、增加。

该算法将比上述尝试快得多。

于 2013-03-01T20:59:52.777 回答
2

我会尝试两件事。它们都基于以下想法：

如果我们能解决判断是否有k元素总和为的p问题，那么我们可以对 中的答案进行二分搜索[1, m]。

1.优化暴力破解

当当前总和超过 时，只需对数组进行排序并缩短搜索时间p。这个想法是您通常只需很少回溯，因为排序数组应该有助于及早消除不良解决方案。

老实说，我怀疑这是否足够快。

2.一种随机算法

保留一个usedsize 的数组k。随机分配元素给它。虽然它们的总和不是p，但随机替换一个元素并确保在恒定时间内更新它们的总和。

继续这样做最多e次数（用它的值进行实验以获得最佳结果，复杂性最终会达到O(e log m)，所以它可能会变得相当高），如果你p在这段时间内无法求和，假设它不是可能的。

或者，忘记二分搜索。直接运行随机算法并返回它在运行中找到的最大有效总和，e或者直到您分配的运行时间结束。

我不确定 DP 如何有效地跟踪总和中使用的元素数量。我认为随机算法值得一试，因为它很容易实现。

于 2013-02-27T20:01:28.910 回答
0

对于 l <= k 和 r <= s：

V[l][r] = true 如果有可能恰好选择总和为r的l 个元素。

V[0][0] = true
for i in 1..n:
  V'[][] - initialize with false
  for l in 0..k-1:
    for r in 0..s:    
      if V[l][r] and s + a[i] <= s:
        V'[l + 1][r + a[i]] = true
  V |= V'

这为您提供了 O(k * n * s) 中所有可实现的总和。

于 2013-03-01T22:00:49.193 回答
0

我认为 Tyler Durden 的想法是正确的。但是您不必对所有元素求和，而且您基本上可以贪婪地完成它，因此您可以大大减少循环。在 C++ 中：

#include <iostream>
#include <algorithm>
using namespace std;

#define FI(n) for(int i=0;i<(n);i++)

int m, n, k;
int a[] = { 12, 43, 1, 4, 3, 5, 13, 34, 24, 22, 31 },
    e[20];

inline int max(int i) { return n-k+i+1; }

void print(int e[], int ii, int sum)
{   cout << sum << '\t';
    FI(ii+1) cout << e[i]<<','; cout<<'\n';
}

bool desc(int a, int b) { return a>b; }

int solve()
{   sort(a, a+n, desc);
    cout <<"a="; FI(n) cout << a[i]<<','; cout<<"\nsum\tindexes\n";
    int i,sum;
    i = e[0] = sum = 0;
    print (e,i,a[0]);
    while(1)
    {   while (e[i]<max(i) && sum+a[e[i]]>=m) e[i]++;
        if (e[i]==max(i))
        {   if (!i) return -1;  // FAIL
            cout<<"*"; print (e,i,sum);
            sum -= a[e[--i]++];
        } else // sum+a[e[i]]<m
        {   sum += a[e[i]];
            print (e,i,sum);
            if (i+1==k) return sum;
            e[i+1] = e[i]+1;
            i++;
        }
    }
}

int main()
{   n = sizeof(a)/sizeof(int);
    k = 3;
    m = 39;
    cout << "n,k,m="<<n<<' '<<k<<' '<<m<<'\n';
    cout << solve();
}

对于 m=36，它给出了输出

n,k,m=11 3 36
a=43,34,31,24,22,13,12,5,4,3,1,
sum indexes
43  0,
34  1,
*34 1,10,
31  2,
35  2,8,
*35 2,8,11,
34  2,9,
35  2,9,10,
35

对于 m=37，它给出

n,k,m=11 3 37
a=43,34,31,24,22,13,12,5,4,3,1,
sum indexes
43  0,
34  1,
*34 1,10,
31  2,
36  2,7,
*36 2,7,11,
35  2,8,
36  2,8,10,
36

（最后一次尝试：对于 m=39，它也给出了正确答案，38） 输出：最后一个数字是总和，它上面的行有索引。带星号的行在回溯之前，因此行的最后一个索引太高。运行时间应该是 O(k*n)。

对不起，难以理解的代码。我可以根据要求清理它并提供解释，但我现在还有另一个项目要到期；）。

于 2013-05-08T09:30:33.413 回答