POJ 1948_TinyMind

　　这是一道二维的01背包，开始没有思路，是看了别人的解题报告才有了大方向，再自己写的。但是自己在细节上还是出了许多问题。

　　dp[][]的两个下表分别表示两条边，如果篱笆的长度刚好等于下标，说明有办法建出这么长的篱笆(比如给了1，3，4可以建成长度为5的篱笆，不能建成长度为6的篱笆)，如果能，就将dp赋为1。由于这里是选择单个篱笆的过程，在这个过程中还不能加入判断是否能构成三角形，比如，再选取最后一块篱笆就构成了三角形，但如果在这里就加入判断，会导致选最后一块篱笆之前，不能构成三角形，这时的dp值为0，dp为0应该表示不能建成这么长的篱笆，而不能同时表示能否建成篱笆和能否构成三角形。判断能否构成三角形只需要在最后遍历的时候选取就行了。

　　我在写这道题的过程中，还犯了一个错误，就是对下面循环的j,k的处理，开始我将它们的下界定为fence[i]，这似乎是没问题的，但是，这里是二维的背包，如果这样会导致在DP过程中j和k都会大于等于fence[i],这样显然是不对的，这受了一维背包的影响。

 for(j=v;j>=0;j--)
        for(k=v;k>=0;k--)
         {
            if((dp[j-fence[i]][k]&&j>=fence[i])||(k>=fence[i]&&dp[j][k-fence[i]]))
                dp[j][k]=1;
　　　　　　}

　　还是老问题，思维不够全面，想当然的将一维背包大于0的限制条件照搬到二维，吸取教训。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX_N 50
#define MAX_LEN 850
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
    int i,j,k,sum=0,dp[MAX_LEN][MAX_LEN],fence[MAX_N],v;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&fence[i]);
        sum+=fence[i];
    }
    v=sum/2;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=v;j>=0;j--)
        {
        for(k=v;k>=0;k--)
        {
            if((dp[j-fence[i]][k]&&j>=fence[i])||(k>=fence[i]&&dp[j][k-fence[i]]))
                dp[j][k]=1;
        }
        }
    }
    int max=0;
    for(i=1;i<=v;i++)
    {
        for(j=1;j<=v;j++)
        {
        if(dp[i][j]&&i+j>sum-i-j)
        {
            double p=sum/2.0;
            int tem=(int)((sqrt(p*(p-i)*(p-j)*(p-sum+i+j)))*100);
            if(tem>max)
            max=tem;
        }
        }
    }
    if(max)
        printf("%d\n",max);
    else
        printf("-1\n");
    }
    return 0;
}

优质内容筛选与推荐>>
1、005-目前主要的测试用例设计方法是什么？
2、服务器响应HTTP的类型ContentType大全
3、培训课题目记录2
4、vb.net 如何从资料表中读取二进制图像
5、Reflection.ReflectionTypeLoadException: 无法加载一个或多个请求的类型。有关更多信息，请检索 LoaderExceptions 属性

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看