学步园

#include <cstdio>
#include <cstring>
int f[1001];
int max(int a,int b)
{
    return (a>b?a:b);
}
void swap(int &a,int &b)//原文swap函数疑有误,此处做了改正
{
    int c = a;
    a = b;
    b = c;
}
int main()
{
    int i,j,m,n,x,v[1001],big=1,total,tmp;
    while (scanf("%d %d",&m,&n)!=EOF)//两人limit
    {
        memset(f,0,sizeof(f));
        scanf("%d",&x);//包裹数
        total=0;//总重量
        for (i=1;i<=x;i++)
        {
            scanf("%d",&v[i]);
                if (v[i]>v[big]) big=i;//index标记最大
            total+=v[i];
        }
        swap(v[big],v[x]);
        for (i=1;i<=x;i++)
        {
            tmp=f[m];//tmp用来保存f[i-1,j]
            for (j=m;j>=v[i];j--)//依然是做了倒序降维处理
                f[j]=max(f[j-v[i]]+v[i],f[j]);
        }

        //第二个人就不用dp了,直接看总和就可以判断能不能搬走
        //只需要dp找出第一个人所能搬走的最大重量,不一定把背包装满
        //f[i]可以表示将物品装入容量为i的背包的最大总体积
        //特殊之处在于,value和capacity是同一个,当然需要考虑装不进去的情况
        //将二维优化为一维,隐藏了取x个物体的枚举
        //因此同样是逆序遍历
        if ((total-f[m])<=n) printf("Yes\n");//两个人能把全部搬走
        else if ((total-v[x]-tmp)<=n) printf("Need a helper\n");//除了最重的能搬走
        else printf("No\n");
    }
    return 0;
}

这仍然是个dp，就是一个简单的背包。

http://blog.sina.com.cn/s/blog_6d6add550100ypqp.html

文章来源,内容有改正.