Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求大侠看看,2进制多重背包,死活过不了#include<iostream> #include<cmath> using namespace std; int num[6]; int main(){ int index = 1; int status[120001] = {0}; while(1) { int total = 0; for (int i = 0; i < 6 ; i++) { cin>>num[i]; total += num[i]*(i+1); } if (total == 0) { break; } cout<<"Collection #"<<index++<<":"<<endl; if(total %2 != 0) { cout<<"Can't be divided."<<endl<<endl; continue; } total /= 2; memset(status, 0, total*sizeof(int)); for (int i = 0; i <= total; i++) { if (i <= num[0]) { status[i] = 1; } else { status[i] = 0; } } for (int i = 1; i < 6; i++) { int k = log(num[i]+1.0) / log(2.0); for (int j = 0; j <= k; j++) { for (int sum = total; sum >= 0; sum--) { int temp; if (j < k) { temp = sum-(i+1)*(int)pow(2.0, j); } else { temp = sum - (i+1)*(num[i] - (int)pow(2.0, j) + 1); } if (status[sum] == 0 && temp >= 0) { status[sum] = status[temp]; } if (sum == total && i == 5 && j == k) { break; } } } } if (status[total] == 1) { cout<<"Can be divied."<<endl; } else { cout<<"Can't be divided."<<endl; } cout<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator