2 qq 33312212 qq_33312212 于 2016.03.20 21:28 提问

求大神看看这两个代码差别在哪里,运行结果不同啊 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;
 }

图片说明

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

1个回答

devmiao
devmiao   Ds   Rxr 2016.03.20 22:41
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
poj1014
//============================================================================ // Name : 1014.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hell
POJ1014
Description Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles
POJ1014解题报告
Dividing Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 43674   Accepted: 10841 Description Marsha and Bill own a collection of marbles. They want to split th
POJ1014 Dividing 题解&代码
二进制优化写跪好几次感觉有点醉= =果然是好久没写dp都忘了#include<iostream> #include<stdio.h> #include<string.h> using namespace std; bool flag; int T,a[10],dp[60005],tot,now,temp,x; int main(void) { while(true) {
再次理解DFS(POJ1014)
原题目:http://poj.org/problem?id=1014 题目大意: 有分别价值为1,2,3,4,5,6的6种物品,输入6个数字,表示相应价值的物品的数量,问一下能不能将物品分成两份,是两份的总价值相等,其中一个物品不能切开,只能分给其中的某一方,当输入六个0是(即没有物品了),这程序结束,总物品的总个数不超过20000   输出:每个测试用例占三行:
POJ1014:Dividing
Dividing Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 63013   Accepted: 16315 Description Marsha and Bill own a collection of marbles. They want to split
求大神们看看哪里出错了
ImageView img1; Button bt1, bt2; int j=0; Drawable d[] = { this.getResources().getDrawable(R.drawable.horse1), this.getResources().getDrawable(R.drawable.horse2), this.getResources().getDrawable(
再次理解dfs,poj1014
#include #include #include #include #include using namespace std; int a[7] = {0}; int flag = 0; int half = 0; void dfs( int value, int cus) {     if (value == half){         flag
求大神看看哪里有问题
package Test; import javax.swing.*; import java.awt.*; import java.awt.event.*; public class Change extends JFrame implements ActionListener,ItemListener{    JTextField jT1,jT2;  JLabel jL1,jL2
POJ1014 - 多重背包
题意: 有六种价值的矿石..各有N [ i ] 个...问两个人能否分得同样多价值的矿石      将总价值算出来..TotolValue = ( N [ 1 ] * 1 + N [  2 ]  * 2 + N [ 3 ] * 3 + N [ 4 ] * 4 + N [ 5 ]