我从未接触过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;
}
动态规划的思想是迭代地计算答案，在每一步上使用已经在前面步骤中计算出的答案。现在让我们看看如何为您的问题实现它：
令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个石头本身的重量添加到循环后的集合中，以避免出现不可能的重量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;
for (int stone : a) 和 for (int partial : reachable) 来插入 stone + reachable。 - Caleth1 - 如果你在编写ACM代码，请避免使用动态分配/ new。它会使程序变慢，也容易导致段错误。尝试通过查看问题陈述中的边界来静态分配所有内容。
2 - 你想要解决的问题是背包问题。如果愿意，现在可以在互联网/维基百科上找到大量资源和解决方案。
3 - 动态规划的关键在于使用缓存，只需要计算递归函数的值一次。在你的情况下，有2^n种可能的石头分割方式，但假设每个石头的最大重量为W，则一组石头只有n*W种可能的重量。
那么，我们能否制定一个函数F(w)，确定是否存在一组石头使它们的总重量为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(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的诀窍在于准确地注意到我们将为此函数使用有限数量的输入（从0到NROCKS * max（MAXWEIGHT）的W和从0到NROCKS的N），因此我们可以使用NROCKS * MAXWEIGHT乘以NROCKS矩阵（或类似物）作为查找表，以避免重复计算。
std::vector<int>代替动态分配的int数组来简化代码。 - Frerich Raabe