Dividing POJ - 1014 多重背包二进制优化

多重背包模型  写的时候漏了一个等号找了半天 i<<=1 !!!!!!

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[];
int dp[];
int m[];
int main(){
int n=;
int kase=;
while(scanf("%d",&a[])==){
int sum=a[];
int flag=;
for(int j=;j<=a[];j<<){
m[flag++]=j;
a[]-=j;
}
if(a[])m[flag++]=a[];
for(int i=;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
for(int j=;j<=a[i];j<<=){
m[flag++]=j*(i+);
a[i]-=j;
}
if(a[i])m[flag++]=a[i]*(i+);
} memset(dp,,sizeof(dp));
if(sum==)break;
sum=;
for(int i=;i<flag;i++)sum+=m[i];
if(sum&){
printf("Collection #%d:\nCan't be divided.\n\n",kase++);
continue; }
for(int i=;i<flag;i++){
for(int j=sum/;j>=m[i];j--){
dp[j]=max(dp[j],dp[j-m[i]]+m[i]);
}
}
if(dp[sum/]==sum/)printf("Collection #%d:\nCan be divided.",kase++);
else printf("Collection #%d:\nCan't be divided.",kase++);
puts("");
puts(""); }
return ;
}
上一篇:系列文章--SharePoint 2013 Designer 入门教程


下一篇:《安卓网络编程》之第四篇 处理URL地址