动态编程

Question

从来没有必要处理DP.
我们有N块石头,重量为W_1,...,W_N.需要将所有宝石分成两部分,它们之间的差异很小.

由于我们有n = 6,而权重= 1,4,5,6,7,9,因此差异为0.

#include <iostream>

using namespace std;

int main()
{
    int     n; // numbers of stones
    int*    a; // array of weights
    int diff=0;
    cin >> n;
    a = new int[n];
    for(int i=0;i<n;i++)
        cin >> a[i];

    // And I don't know what's next, mee too

    delete[] a;
    system("PAUSE");
    return 0;
}

Answer 1

动态编程的想法是使用已经在先前步骤计算的答案在每个步骤上迭代地计算答案.让我们看看如何为您的问题实现这一点:

让我们sum成为所有元素的总和:

int sum = 0;
for( int i = 0; i < n; ++i )
   sum += a[ i ];

让我们构造一个reachable集合,其中包含可以在单个部分中实现的所有可能的总和:

std::set< int > reachable;
for( int i = 0; i < n; ++i )
{
   for( set< int >::iterator it = reachable.begin(); it != reachable.end(); ++it )
      reachable.insert( *it + a[ i ] );
   reachable.insert( a[ i ] );
}

注意DP在这里是如何工作的:已经构建了所有可能的总和,这些总和可以使用第一i - 1块石i头来实现,我们尝试为每块石头添加石头以获得i石头的所有可能总和.此外,我们在循环后添加重量if i-th stone本身到集合,以避免获得不可能的重量a[ i ] + a[ i ](因为每块石头最多可以使用一次).在这一步之后,我们得到所有可能的重量,每个石头最多使用一次.

显然,如果一个部分的重量是*it(设定元素之一)那么其他部分的重量将是sum - *it,所以它们的差异将是fabs( sum - 2 * (*it)).让我们找到最小值:

diff = sum; // maximal difference, when all stones are in one part
for( set< int >::iterator it = reachable.begin(); it != reachable.end(); ++it )
   diff = min( diff, fabs( sum - 2 * (*it) ) );
std::cout << "The answer is " << diff << std::endl;

Answer 2

1 - 如果要编写ACM编码,请避免动态分配/ new.它较慢,是段错误的esay源.尝试通过查看问题陈述的边界来静态分配所有内容.

2 - 您要解决的问题是背包问题.如果您愿意,您现在可以在互联网/维基百科上找到大量的资源和解决方案.

3 - 与DP的交易使用缓存只需要计算一次递归函数的值.在你的情况下,你有2 ^ n可能的石头spplitings,但假设每块石头的最大重量W,一组石头只有n*W可能的重量.

那么,我们可以制作一个函数F(w)来确定是否有一组石头加起来？如果是这样,我们可以找到一个只有n*W次迭代而不是2 ^ n的算法!

答案是肯定的!但是你可能需要进行一些排序才能使其正常工作.设G(w,n)定义为:

G(w, n) =
    (true, s) if there is some set s containing only from the first n stones 
                 that adds up to w
    (false, _) if there is no such set.

我们现在需要做的就是计算G(w,NROCKS)来找到F(w)!

很容易找到允许我们计算G的递归定义:

G(0, 0) = (true, {})
G(W, 0) = (false, _)
G(W, N) = 
    G(W, N-1)  //we don't use the N-th rock -
               //find solution with remaining rocks instead.
    OR G(W - w(N), N-1)  //if we use the N-th rock, assumin its wheigh is given by w(N)
                         //our problem reduces to seeing if it is possible to add up to
                         // W - w(N) using only the remaining rocks

虽然你可以直接实现这个函数,它仍然会有一个指数运行时(我不想解释这个.但想想传统的斐波那契函数的例子).

DP的技巧,正是注意到我们将用于此功能的输入数量有限(W从0到NROCKS*max(MAXWEIGHT),N从0到NROCKS),所以我们可以使用NROCKS*MAXWEIGHT通过NROCKS矩阵(或类似的东西)作为查找表,以避免计算两次.