URAL——1005 stone pile-蒲公英云

URAL——1005 stone pile

题意：

给你n个石头（1<=n<=20），给出每个石头的重量w[i]( 1<=w[ i ] <= 100000),均分为两堆，求出两堆最小的差距重量，并输出。

这一题有两种解法，一时dfs搜出每种情况，二是动态规划求解问题。

#include<iostream>
#include<stdlib.h>
#define maxn 27
#define INF 20000007
using namespace std;
long n,sum,ans,w[maxn];
void dfs(long dep,long now)
{
    if(dep>n)
    {
        if(ans>abs(now-(sum-now))) ans=abs(now-(sum-now));
        return;
    }
    dfs(dep+1,now);
    dfs(dep+1,now+w[dep]);
}
int main()
{
    cin>>n;
    sum=0;
    for(long i=1;i<=n;i++)
    {
        cin>>w[i];
        sum+=w[i];
    }
    ans=INF;
    dfs(1,0);
    cout<<ans<<endl;
return 0;
}

复杂度为2^n,因为n值很小，此方法对这一题求解较优

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#define N 1000010
int w[22],object[N];
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int sum=0,half,i,j; 
        for(i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            sum+=w[i];
        }
        half=sum/2;
         for (i=1;i<=n;i++)
        {
            for (j=half;j>=w[i];j--)
                object[j] = max(object[j], object[j-w[i]]+w[i]);
        }
        cout<<sum-object[half]*2<<endl;
    }
     return 0;
}