问题描述

求大神看看这两个代码差别在哪里，运行结果不同啊 poj1014

错误代码及运行结果

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t=0,i,v;
int n[7];
int dp[60001];

bool flag =false;
int imax(int a,int b)
{
    return (a>b?a:b);
}

void comepletepack(int cost,int weight)
{
    for(i=cost;i<=v;++i)
    {
        dp[i]=imax(dp[i],dp[i-cost]+weight);
        if(dp[i]==v)
        {
            flag =true;
            return;
        }
    }
}
void onezeropack(int cost,int weight)
{
    for(i=v;i>=cost;--i)
    {
        dp[i]=imax(dp[i],dp[i-cost]+weight);
        if(dp[i]==v)
        {
            flag =true;
            return;
        }
    }
    return;
}
void mutipack(int cost,int weight,int amount)
{
    if(cost*amount>=v)
    {
        comepletepack(cost,weight);
        return;
    }
    if(flag)
        return;
    int k=1;
    while(k<amount)
    {
        onezeropack(k*cost,k*weight);
        if(flag)
        return;
        amount-=k;
        k*=2;
    }
    onezeropack(amount*cost,amount*weight);

}

int main()
{
    int sum;
    while(scanf("%d %d %d %d %d %d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]))
    {
        ++t;
        sum =n[1]+2*n[2]+3*n[3]+4*n[4]+5*n[5]+6*n[6];
        if(sum==0)
        break;
        if(sum%2!=0)
        {
            cout<<"Collection #"<<t<<':'<<endl;
            cout<<"Can't be divided."<<endl;
            cout<<endl;
            continue;
        }
            v=sum/2;
            memset(dp,-1,sizeof(dp));
            dp[0]=0;
            flag =false;
            for(i=1;i<=6;++i)
            {
                mutipack(i,i,n[i]);
                if(flag)
                break;
            }

        if(!flag)
        {
            cout<<"Collection #"<<t<<':'<<endl;
            cout<<"Can't be divided."<<endl;
            cout<<endl;
        }
        else
        {
            cout<<"Collection #"<<t<<':'<<endl;
            cout<<"Can be divided."<<endl;
            cout<<endl;
        }
    }
    return 0;
}

正确代码及其运行结果

 #include<iostream>
#include <cstring>
   using namespace std;

   int n[7];  //价值为i的物品的个数
  int v;  //背包容量
  int SumValue;  //物品总价值
  bool flag;    //标记是否能平分SumValue
  int dp[100000];  //状态数组

  int max(int a,int b)
  {
      return a>b?a:b;
  }

  /*完全背包*/
 void CompletePack(int cost,int weight)
  {
      for(int i=cost;i<=v;i++)
      {
          dp[i]=max(dp[i],dp[i-cost]+weight);
          if(dp[i]==v)    //剪枝，当能够平分SumValue时退出
          {
              flag=true;
              return;
          }
      }

      return;
  }

  /*01背包*/
  void ZeroOnePack(int cost,int weight)
  {
      for(int i=v;i>=cost;i--)
     {
          dp[i]=max(dp[i],dp[i-cost]+weight);
          if(dp[i]==v)    //剪枝
          {
              flag=true;
              return;
          }
      }
      return;
  }

 /*多重背包*/
  void MultiplePack(int cost,int weight,int amount)
  {
      if(cost*amount>=v)
      {
          CompletePack(cost,weight);
          return;
      }

      if(flag)    //剪枝
          return;

      /*二进制优化*/
      int k=1;
      while(k<amount)
      {
          ZeroOnePack(k*cost,k*weight);

          if(flag)    //剪枝
              return;

          amount-=k;
          k*=2;
      }
      ZeroOnePack(amount*cost,amount*weight);

     return;
  }

  int main(int i)
  {
      int test=1;
      while(cin>>n[1]>>n[2]>>n[3]>>n[4]>>n[5]>>n[6])
      {
          SumValue=0;  //物品总价值

          for(i=1;i<=6;i++)
              SumValue+=i*n[i];

          if(SumValue==0)
              break;

          if(SumValue%2)    //sum为奇数，无法平分
          {
              cout<<"Collection #"<<test++<<':'<<endl;
              cout<<"Can't be divided."<<endl<<endl;    //注意有空行
              continue;
          }

         v=SumValue/2;
         memset(dp,-1,sizeof(dp));
        dp[0]=0;
         flag=false;

         for(i=1;i<=6;i++)
         {
             MultiplePack(i,i,n[i]);

            if(flag)    //剪枝
                 break;
         }

        if(flag)
         {
             cout<<"Collection #"<<test++<<':'<<endl;
            cout<<"Can be divided."<<endl<<endl;
             continue;
         }
        else
         {
             cout<<"Collection #"<<test++<<':'<<endl;
            cout<<"Can't be divided."<<endl<<endl;
             continue;
       }
     }
     return 0;
 }

求大神看看错的错在哪里了

解决方案

http://www.cnblogs.com/lyy289065406/archive/2011/08/04/2128033.html