HDU 1059 DP （完全背包 && 多重背包）

题意 ： 给你6堆钻石，每一堆钻石的价值为 i 每一堆钻石有 i 个 问你能不能平分

题解 ： 这种问题一般来说应该是dp… 当然这个也不例外。dp (i) 表示 能不能用这么多钻石表示出 i 这么多的价值 dp 的取值为 0 / 1 表示不可以和可以。这样的话我们就可以进行转移了

如果dp (i) = 1 的时候我们才进行转移 通过这种状态转移到后面的所有可能状态 dp (i + k * j) = 1; 这种转移 注意 ：：：当我们在转移的过程中发现如果有一个值已经被设置成1的时候，后面的一定已经都被设置成1了 （因为我们每次都是转移的一个相同的数）；具体看代码吧 （注意转移的方向非常重要，是从大到小还是从小到大要考虑好）
           

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int maxn = ;
int dp[maxn] = {};
int num[] = {};

int main () {
    ios_base :: sync_with_stdio(false);
    int cas = ;
    while (cin >> num[] >> num[] >> num[] >> num[] >> num[] >> num[]) {
        if (!(num[] + num[] + num[] + num[] + num[] + num[])) break;
        cout << "Collection #"<< cas ++ << ":" << endl;
        memset (dp,,sizeof(dp));
        int sum = ;
        for (int i = ;i <= ; ++ i) {
            sum += (i * num[i]);
        }
        if (sum % ) {
            cout << "Can't be divided." << endl;
            cout << endl;
            continue;
        }
        int u = sum / ;
        dp[] = ;
        int mx = ;
        for (int i = ;i <= num[]; ++ i) dp[i] = ;
        mx = num[];
        for (int i = ;i <= ; ++ i) {
            for (int j = mx;j >= ;-- j) { // 防止选重复了
                if (dp[j]) {
                    for (int k = ;k <= num[i] && k * i + j <= u; ++ k) {
                        if (dp[j + k * i]) break; // 因为每次都是加上 i 并且顺序是从后往前 所以这个可以直接break掉就好了这个剪枝的力度是非常大的可以考虑一下，相当于我所有的k ++ 的总次数都不会超过 num[i] * i 这个数量级 相比于 mx * num[i] 不知道高到哪里去了 
                        dp[j + k * i] = ;
                    }
                }
            }
            mx = mx + num[i] * i;
        }
        if (dp[u]) {
            cout << "Can be divided." << endl;
        }
        else {
            cout << "Can't be divided." << endl;
        }
        cout << endl;
    }
    return ;
}