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 ;
}