2 qq 33312212 qq_33312212 于 2016.03.20 18:32 提问

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的物品直到装满了吗?
有说的不对的 还希望大神能耐心解释

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
背包问题总结(01背包、完全背包、多重背包)
1、 01背包问题 有n个物品,每个物品只有一件。 动归方程: (1)  二维数组解法      dp[i][j]=max{dp[i-1][j-w[i]]+v[i] , dp[i-1][j]}; (2)  一维数组解法      dp[j]=max{dp[j-w[i]]+v[i] , dp[j]} 附代码: HDU 2602 Bone Collector 二维数组: #in
DP背包问题小结(01背包,完全背包,需恰好装满或不需,一维DP、二维DP)
1) 01背包基础,求背包所装物品价值之和的最大值,不要求恰好装满时,采用易于理解的二维DP数组存储。 #include #include using namespace std; int dp[1010][1010]; int vp[1010]; int wp[1010]; int main() { int kase;cin>>kase; while(kase--)
FZU 2214 Knapsack problem【DP】【超大容量背包】
题目链接http://acm.fzu.edu.cn/problem.php?pid=2214思路咋一看是个01背包问题,但背包容量很大,有10910^9,数组肯定开不下,所以要换种思路。就是设dp[i]为拿到总价值为i的物品时所需的最小的背包容量,那么dp[tot_v]=tot_w,其他初始化为INF,然后对于第i个物品,遍历所有价值j,dp[j-v[i]]=min(dp[j-v[i]],dp[j]
背包问题的二进制优化
关于二进制优化这一点,它为什么正确,为什么合理,凭什么可以这样分,至少我是花了很久很久才理解的,先拿一道题来说吧。 HDU 2844 Coins 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2844 题目: Coins Time Limit: 2000/1000 MS (Java/Others)    Memory Limit
完全背包问题dp
完全背包
背包问题小总结 习题(动态规划01背包(第k优解)完全背包,多重背包)acm杭电HDU2639,HDU2602,HDU1114,HDU2191
1、01背包(每种物品只有一个)2、多重背包,完全背包 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。 求解将哪些物 品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态: 即表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。 则其状态转
DP背包之01背包、完全背包、多重背包笔记
这是个经典话题,值得好好研究一番,本文作为学习笔记将会不断更新。 主要参考了以下资料: 背包问题九讲:http://love-oriented.com/pack/Index.html 背包之01背包、完全背包、多重背包详解 :http://www.wutianqi.com/?p=539 背包问题九讲笔记_01背包:http://blog.csdn.net/insistgogo/ar
01背包 ,完全背包,多重背包 dp (动态规划入门dp)
dp 动态规划,确实难啃, 光 最简单的 背包问题,就 费老大劲. 思想! 思想! 思想!   类似于递推, 局部找 关系.  背包问题,  就两种状态  放还是不放?   其实关于背包放不放的问题,如果用二进制思想来表示的话 很好理解,  0 代表不放 1 代表放;   那么对于现有的情况  假设有 n个物品 则 2进制则对应的长度应该为n 对于每一个物品用0 1 表示 000xx~~~1
多重背包问题 详细推导
多重背包问题(每种物品数量有限)   问题重现: 有n种物品和一个容量为m的背包。每件物品的体积为w1,w2……wn,与之相对应的价值为p1,p2...pn,但是每件物品的数量对应为num1,num2...numn 从其中选出若干物品装入背包可使这些体积总和不超过背包容量,求出获得最大价值的方案。 子问题状态定义:c[i][m]表示在前i种物品选择若干放入容量为m的背包的最大价值 此时
中级篇——背包问题3(多重背包)
上一篇讲的完全背包是指在所有物品件数无限多的情况下选择最值,现在引申出多重背包问题,即各物品个数均有限且不一定相同,求轙类情况下的最值。