首页 > 代码库 > POJ 1014 Dividing【多重背包+二进制优化】

POJ 1014 Dividing【多重背包+二进制优化】

2024-07-20 01:35:43   214人阅读

大意：

价值1， 2， 3， ……， 6的物品分别a1， a2， ……， a5， a6件

问能否把这些物品分成两份，使其具有相同的价值（所有物品必须全部用上）

 

分析：

给个物品有多件，即多重背包

只要看能不能将这些物品拼成   总价值 的 一半就可以了

转化为01背包是用二进制优化，否则会超时

 

代码：

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6 const int maxn = 20005 * 6; 7  8 int n, all; 9 int vo[maxn];10 int dp[maxn];11 bool solve() {12     if(all % 2 == 1) return false;13     all /= 2;14     memset(dp, 0, sizeof(dp));15     for(int i = 1; i <= n; i++) {16         if(vo[i] > all) return false;17         for(int j = all; j >= vo[i]; j--) {18             dp[j] = max(dp[j], dp[j - vo[i]] + vo[i]);19         }20     }21     if(dp[all] != all) return false;22     return true;23 }24 25 int main() {26     int a[10];27     int kase = 1;28     while(scanf("%d %d %d %d %d %d",&a[1], &a[2], &a[3], &a[4], &a[5], &a[6]) ) {29         all = 0;30         for(int i = 1; i <= 6; i++) {31             all += a[i] * i;32         }33         if(all == 0) break;34         n = 1;35         for(int i = 1; i <= 6; i++) {36             for(int k = 1; k <= a[i]; k *= 2) {37                 vo[n++] = k * i;38                 a[i] -= k;39             }40             if(a[i]) vo[n++] = a[i] * i;41         }42         n--;43         printf("Collection #%d:\n", kase++);44         puts(solve() ? "Can be divided." : "Can‘t be divided.");45         puts("");46     }47     return 0;48 }
View Code

 

POJ 1014 Dividing【多重背包+二进制优化】


联系
我们