51nod1007-正整数分组（dp）

题目：http://www.51nod.com/Challenge/Problem.html#!#problemId=1007

　　大意就是给一堆正整数，分成和最接近的两组。

　　最开始没什么想法，2^n尝试肯定TLE。查了查发现用的居然是dp.于是又回去看了一下dp算法，大概理解了。

　　先贴ac代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int MAX = ;

int source[];

int r[][MAX+];

int max(int a,int b)

{

    return (a>b?a:b);

}

int main()

{

    int n=;

    int i=;

    int j=;

    int total=;

    int half=;

    cin>>n;

    for(i=;i<n;i++)

    {

        scanf("%d",&source[i]);

        total+=source[i];   //记得考虑最后total是奇数的情况。

    }

    half=(total% ==  ?total/:total/+);

    for(i=;i<;i++)

    {

        r[i][]=;

    }

    for(i=;i<n;i++)

    {

        for(j=;j<=half;j++)

        {

            if(source[i]>j)  //r[i][j-1]=r[i-1][j]=r[i-1][j-1]

            {

                r[i][j]=r[i][j-];

            }

            else

            {

                if(i == )

                {

                    r[i][j]=+source[i];

                }

                else

                {

                    r[i][j]=max(r[i-][j],r[i-][j-source[i]]+source[i]);

                }

            }

        }

    }

    cout<<abs(total-*r[n-][half]);

    return ;

}

　　之前在网上查，大部分人都说是01背包，但当时怎么都理解不了……于是换了一种思路：

　　dp方法最关键的步骤在于对于要求的问题 Q(n) ,它的答案一定是和之前求过的答案 Q(0) , Q(1) , Q(2) ... Q(n-1) 中的某个答案是有关系的。就这道题目来说，思考的方法是：记Q(n)为给定数中和不超过n的最大组合。就是给定数随便挑，只要和不大于n就行，我们要的是和最大的那组。

　　虽然是给定数随便挑，但我们也只能从第一个开始一个一个地看啊。于是，用记m为我们已经看了多少个数。

　　于是关键来了。假设我们从前m个数中，找到了一组小于n的最大值（仅仅在前m个数中是最大的，对于前m+1个数就不一定了），也就是说，我们暂时找到了Q(n)。但是因为所有的数还没看完，同时n还没达到目标（所有数的总和除以2）。那么，我们来考虑Q(n+1)，有如下几种情况：

　　1）Q(n)=Q(n-1),也就是说不需要m+1.那么有两种情况不需要：如果m+1>n,那么肯定Q(n)=Q(n-1)。因为m+1本来就不满足“小于n”。而如果m+1<n，那么也有可能不选，即没有合适的组合。那什么情况下没有合适的组合呢？就是从 1 到 m 随便怎么组合，只要加上m+1，要么大于n，要么小于Q(n-1)。

　　2）Q(n)>Q(n-1),根据上面的分析，这里就意味着有这么一个组合，能满足它加上m+1，正好介于Q(n-1)和n之间。那这个组合应该怎么找呢？换个思路，我们要找的Q(n)是小于n的最大和，我们知道这个数是k+(m-1)，而我们现在要找到 最大的k 。而恰好我们已经找到了从0到n-1的所有的最大值，因此那个k肯定在这之中，确切来说就是Q(n-(m+1)).

　　到此，思路就清晰了。

巴特西

51nod1007-正整数分组（dp）

最新文章

热门文章