Dividing二进制背包优化

本文主要是介绍Dividing二进制背包优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

#include<iostream>
#include<string>
#define max(x,y) x>y?x:y
using namespace std;
int dp[150000],w[20010],v[20010];
int main()
{
 int a[10],i,j,t=1,c,num;
 while(1)
 {
  int sum=0;
  for(i=1;i<=6;i++)
  {
   cin>>a[i];
   sum+=i*a[i];
  }
  if(sum==0)
   break;
  if(sum%2==1)
  {
   cout<<"Collection #"<<t<<":"<<endl;
   t++;
   cout<<"Can't be divided."<<endl<<endl;
   continue;
  }
  num=1;
  for(i=1;i<=6;i++)
  {
   c=a[i];
   for(j=1;j<=c;j*=2)
   {
    v[num]=i*j;
    w[num++]=v[num];
    c-=j;
   }
   if(c>0)
   {
    v[num]=i*c;
    w[num++]=v[num];
   }
  }
  sum/=2;
  memset(dp,0,sizeof(dp));
  for(i=1;i<num;i++)
   for(j=sum;j>=v[i];j--)
    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  if(dp[sum]==sum)
  {
   cout<<"Collection #"<<t<<":"<<endl;
   t++;
   cout<<"Can be divided."<<endl<<endl;
  }
  else
  {
   cout<<"Collection #"<<t<<":"<<endl;
   t++;
   cout<<"Can't be divided."<<endl<<endl;
  }
 }
 return 0;
}

这篇关于Dividing二进制背包优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---