k个元素的最大总和不大于m

Question

此问题来自程序设计竞赛，无法在可接受的时间内解决问题。

给出n整数的数组a。找到元素（不一定是连续的）的最大总和s，该值不会超过给定的整数m (s < m)。

限制条件：

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

信息：A液是保证对于给定的输入存在。

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

Answer 1

我会尝试两件事。它们均基于以下理念：

如果如果有k元素就可以解决决定的问题和正是到p，那么我们就可以在[1, m]答案二进制搜索。

1.优化了暴力破解

简单的排序阵列，并且当电流总和超过p削减搜索短。这个想法是，你通常只需要很少的回溯，因为排序后的数组应该尽早消除不好的解决方案。

说实话，我怀疑这个速度会不够快。

2.一种随机算法

保持一个used阵列尺寸k的。随机分配元素给它。虽然他们的总和不是p，但是随机地将一个元素替换为另一个元素，并确保在一段时间内更新它们的总和。

保持这种做最大e倍（实验用其最好的结果值，复杂性将在年底O(e log m)，所以它可以或许走相当高），如果你不能得到在此总结p时间，假设这是不可能的。

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

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

Answer 2

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

以下是通过实施例示出的正确的方法：

想象= {2，3，5，9，11，14，17，23}（因此N = 8）中，k = 3，并且s = 30

排列数组a。

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

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

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

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

现在回到P2并减少一个。

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

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

这个算法比上面的尝试要快很多。

Answer 3

对于l = < K和R < = S：

V [1] [R]当且仅当有可能准确选择升其总结于- [R元素=真。

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）。

Answer 4

我认为泰勒杜登有正确的想法。但是，你不必总结所有的元素，而且基本上可以贪婪地做，所以你可以减少这个循环。在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）。

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