首页 > 代码库 > POJ 1014 Dividing 背包
POJ 1014 Dividing 背包
二进制优化,事实上是物体的分解问题。
就是比方一个物体有数量限制,比方是13,那么就须要把这个物体分解为1。 2, 4, 6
假设这个物体有数量为25,那么就分解为1, 2, 4。 8。 10
看出规律吗,就是分成2的倍数加上位数,比方6 = 13 - 1 - 2 - 4, 10 = 25 - 1 - 2 - 4 - 8。呵呵,为什么这么分解?
由于这样分解之后就能够组合成全部1到13的数。为25的时候能够组合成全部1到25的数啦。
就是这么一个分解物体。最后组合的问题。
不明确?
给多几个数字组合:
31分解 1, 2, 4, 8, 16
32分解1,2,4, 8, 16, 1
33分解1,2,4,8,16,2
如此分解的。
想通了,就和一般背包问题一样做法了。
#include <stdio.h> #include <vector> using std::vector; const int SIZE = 7; int N[SIZE]; bool findPartition() { int sum = 0; for (int i = 1; i < SIZE; i++) sum += i * N[i]; if (sum & 1) return false; int half = sum >> 1; vector<bool> part(half+1); part[0] = true; for (int i = 1; i < SIZE; i++) { int k = 1; for ( ; (k<<1) <= N[i]; k <<= 1) {//例:13分解为1,2,4,6能够组合为1到13个物品。故此考虑了全部情况了 for (int j = half; j >= k*i; j--) { if (part[j-k*i]) part[j] = true; } } k = N[i] - k + 1; for (int j = half; j >= k*i; j--) { if (part[j-k*i]) part[j] = true; } } return part[half]; } int main() { int t = 1; while (true) { int val = 0; for (int i = 1; i < SIZE; i++) { scanf("%d", &N[i]); val += N[i]; } if (!val) return 0; if (findPartition()) printf("Collection #%d:\nCan be divided.\n\n", t++); else printf("Collection #%d:\nCan‘t be divided.\n\n", t++); } return 0; }
POJ 1014 Dividing 背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。