<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12
      書山有徑勤為路>>>>>>>>

      <<<<<<<<學海無涯苦作舟!

      DP(五)——簡單的多重背包

      POJ 1014    http://poj.org/problem?id=1014

      題意是這樣的:有分別價值為1,2,3,4,5,6的6種物品,輸入6個數字,

      表示相應價值的物品的數量,問一下能不能將物品分成兩份,

      是兩份的總價值相等,其中一個物品不能切開,只能分給其中的某一方,

      當輸入六個0是(即沒有物品了),這程序結束,總物品的總個數不超過20000

      Sample Input

      1 0 1 2 0 0 
      1 0 0 0 1 1 
      0 0 0 0 0 0 

      Sample Output

      Collection #1:
      Can't be divided.
      
      Collection #2:
      Can be divided.
      下面一個是個高效的算法,但是不是最高的。
      View Code
      #include<iostream>
      using namespace std;
      #define size 70010
      int f[2*size];
      int a[10];
      int MultP(int n, int v){
          int i, j, k, amount;
          memset(f, 0, sizeof(f));
          for(i=1; i<=n; i++){ //枚舉物品的總數量,(這里數量=價值)
              if(a[i]*i>=v){ //完全背包,(a[i]表示第i件物品的數量) 
                  for(j=i; j<=v; j++)
                      f[j] = max(f[j], f[j-i]+i);     
              }
              else{ //01背包
                  k=1;
                  amount = a[i];
                  while(k<amount){
                      for(j=v; j>=k*i; j--)
                          f[j] = max(f[j], f[j-k*i]+k*i);
                      amount -= k;
                      k = k*2;
                  }
                  for(j=v; j>=amount*i; j--)
                      f[j] = max(f[j], f[j-amount*i]+amount*i);
              }
          }
          return f[v];
      }
      int main()
      {
          int Case=0, flag, i, sum;
          while(1)
          {
              Case++;
              sum = 0;
              for(i=1; i<=6; i++)
              {
                  cin>>a[i];
                  sum+=a[i]*i;
              }
              flag = 0;
              for(i=1; i<7; i++)
              {
                  if(a[i]!=0)
                  {
                      flag = 1;
                      break;
                  }
              }
              if(flag == 0) break;
              if(sum%2==1)
              {
                  cout<<"Collection #"<<Case<<":"<<endl<<"Can't be divided."<<endl<<endl;
                  continue;
              }
              i = MultP(6, sum/2);
              if(i==(sum/2)) cout<<"Collection #"<<Case<<":"<<endl<<"Can be divided."<<endl<<endl;
              else cout<<"Collection #"<<Case<<":"<<endl<<"Can't be divided."<<endl<<endl;
          }
      }

       

      下面給出一個不是很高效的算法,在POJ上是超時的。
      
      
      View Code
      #include<iostream>
      using namespace std;
      #define size 20005
      int num[7];
      bool f[size];
      int main()
      {
      int ex = 0, sum, i, j, k, Max, t, flag;
      while(cin>>num[0]>>num[1]>>num[2]>>num[3]>>num[4]>>num[5])
      {
      ex++;
      sum=0, flag=0;
      for(i=0; i<6; i++) sum+=num[i]*(i+1);
      if(sum==0) break;
      if(sum%2==1)
      {
      cout<<"Collection #"<<ex<<":"<<endl<<"Can't be divided."<<endl<<endl;
      continue;
      }
      //接下來多重背包
      Max = 0;
      f[0] = true; //這個是初始化問題
      for(i=0; i<6; i++) //枚舉每件物品
      {
      for(k=Max; k>=0; k--) //01背包的做法
      {
      if(f[k]==true) //判斷此時f[k]是否已經存在,只有存在了,才可以繼續DP
      {
      for(j=1; j<=num[i]; j++) //件數,從1開始
      {
      t = k+j*(i+1); //此時的價值
      f[t] = true;
      if(t>Max) Max = t;
      if(Max==(sum/2))
      {
      flag = 1;
      break;
      }
      }
      }
      if(flag) break;
      }
      if(flag) break;
      }
      if(flag) cout<<"Collection #"<<ex<<":"<<endl<<"Can be divided."<<endl<<endl;
      else cout<<"Collection #"<<ex<<":"<<endl<<"Can't be divided."<<endl<<endl;
      }
      }


       

      posted on 2011-11-16 21:40  More study needed.  閱讀(272)  評論(0)    收藏  舉報

      導航

      書山有徑勤為路>>>>>>>>

      <<<<<<<<學海無涯苦作舟!

      主站蜘蛛池模板: www亚洲精品| 好男人官网资源在线观看| 综合欧美视频一区二区三区| 久久精品蜜芽亚洲国产AV| 九九热在线视频只有精品| 国产桃色在线成免费视频| 精品无套挺进少妇内谢| 天堂√最新版中文在线地址| 一区二区偷拍美女撒尿视频| 国产av不卡一区二区| 久久亚洲国产欧洲精品一| 美女裸体黄网站18禁止免费下载 | 东京热加勒比无码少妇| 午夜福利国产区在线观看| 国产精品一码在线播放| 国偷自产一区二区三区在线视频| 亚洲天堂网中文在线资源| 亚洲国产成人无码av在线影院 | 久久夜色精品国产亚洲a| 亚洲人成网站77777在线观看| 国产对白老熟女正在播放| 亚洲香蕉av一区二区蜜桃| 办公室强奷漂亮少妇视频| 久热这里只有精品12| 亚洲精品久久久久午夜福禁果tⅴ 免费看美女被靠到爽的视频 | 浴室人妻的情欲hd三级国产| 拜城县| 一区二区三区午夜福利院| 国产精品亚洲二区在线播放| 国产边摸边吃奶边叫做激情视频 | 中文字幕人妻色偷偷久久| 亚洲国产午夜精品理论片| 国产亚洲日韩在线aaaa| 国产精品自拍实拍在线看| 伊人久久大香线蕉AV网| 国产一区二区三区九精品| 久章草在线毛片视频播放| 欧洲中文字幕一区二区| 国产亚洲av产精品亚洲| 色8久久人人97超碰香蕉987| 国产啪视频免费观看视频|