本文主要是介绍Dividing[多重背包]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
多重背包二进制优化
f[i]=1表示i出现过
#include<cstdio>
#include<vector>
#include<cstring>
#define N 200050
using namespace std;
int f[N],a[10],flag,sum,k;
vector<int> v;
void Yes(int x){printf("Collection #%d:\nCan be divided.\n\n",x);}
void No(int x){printf("Collection #%d:\nCan't be divided.\n\n",x);}
int main(){while(1){k++; sum=0; v.clear(); memset(f,0,sizeof(f));for(int i=1;i<=6;i++){scanf("%d",&a[i]); sum+=a[i]*i;for(int j=1;j<=a[i];j<<=1)v.push_back(i*j),a[i]-=j;if(a[i]) v.push_back(i*a[i]);}if(sum==0) break;if(sum&1) No(k);else{sum/=2 , f[0]=1;for(int i=0;i<v.size();i++){for(int j=sum;j>=v[i];j--)f[j]|=f[j-v[i]];}if(f[sum]) Yes(k); else No(k); }}return 0;
}
这篇关于Dividing[多重背包]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
