qq_33312212 2016-03-20 10:32 采纳率: 21.9%
浏览 1128

ACM菜鸟新手 DP多重背包问题 求大神解答

 #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;
 }

求大神解答 这段代码中的这一部分

 void MultiplePack(int cost,int weight,int amount)
  {
      if(cost*amount>=v)
      {
          CompletePack(cost,weight);
          return;
      }

      if(flag)    //剪枝
          return;

      /*二进制优化*/

为什么 这里要进行完全背包 那不是相当于可以无限次使用 费用为cost 价值为weight的物品直到装满了吗?
有说的不对的 还希望大神能耐心解释

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥15 数学的三元一次方程求解
    • ¥20 iqoo11 如何下载安装工程模式
    • ¥15 本题的答案是不是有问题
    • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
    • ¥15 C++使用Gunplot
    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题