一种物品，限制了数量，那就不能按照完全背包的写法去写了
如果按照01背包的方法去写，如果数量很大，那么必然会超时，那有没有什么好办法呢？
我们先讲神奇的二进制思想
我们都知道，任何一个十进制都能转换成二进制（废话）
那么二进制就会对应着许多二进位（还是废话）
每个二进位都是2的倍数（肯定啊）
所以反过来讲，任何一个数字，都能由2的倍数相加组成(........)
再来看一个二进位111111(2),一共有6个二进位，对应的数字分别是32,16,8,4,2,1
那么，我只用这6个数字，我就能描述出1~63中所有的情况了..
其实道理很明白哇，64的二进制是1000000(2)，63的二进制是111111(2)
所以只要小于63的，都能通过那些二进位重新组成这个数字
说二进制思想有什么用呢？假如我们的n等于63,本来如果我用01背包，我需要做63次
如果我用二进制思想去分解n，可以得到32,16,8,4,2,1,那么我只需要拿这6个去做01背包，就能表示出所有的情况了
换句话说，在枚举这里的复杂度，从O(n)降到了O(logn)，优化非常明显！
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 5e5 + 5;
const int INF = 0x3f3f3f3f;int A[10];
bool dp[MX];void solve(int t, int V) {//01背包for(int i = V; i >= t; i--) {dp[i] |= dp[i - t];}
}int main() {int ansk = 0;while(~scanf("%d", &A[1])) {memset(dp, 0, sizeof(dp));int V = A[1];for(int i = 2; i <= 6; i++) {scanf("%d", &A[i]);V += A[i] * i;}if(!V) break;printf("Collection #%d:\n", ++ansk);if(V % 2 != 0) {printf("Can't be divided.\n\n");continue;}V /= 2;dp[0] = true;for(int i = 1; i <= 6; i++) {if(!A[i]) continue;int t = 1;while(t < A[i]) {//分解A[i]solve(t * i, V);A[i] -= t;t <<= 1;}solve(A[i] * i, V);//肯定有时候不能完全分解，还会剩下一点点，单独做一次01背包}if(dp[V]) printf("Can be divided.\n\n");else printf("Can't be divided.\n\n");}return 0;
}