【HDU 1059】Dividing（多重背包）

落日映苍穹つ 2022-03-09 00:09 181阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1059][http_acm.hdu.edu.cn_showproblem.php_pid_1059]

题意：有6种物品，价值分别是1,2,3,4,5,6，每种物品有n\[ i \]个，,问是否能将其平分。

思路：分析可知这是一个多重背包问题，为了简化问题，将多重背包转化成0-1背包，另外，还要注意的是，要将n转化成二进制来优化时间复杂度。（任何数都有![n=k\_\{1\}2^\{0\}+k\_\{2\}2^\{1\}+k\_\{3\}2^\{2\}+...+k\_\{x\}2^\{y\}][n_k_1_2_0_k_2_2_1_k_3_2_2_..._k_x_2_y]）例如7（7=1+2+4）个价值为3的物品，就可以将其转化成3个价值分别为3,6,12的物品，这样就可以减少不少时间。

My Code：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    int v[20005],W,f[150000];
    int main()
    {
        int n[10],t = 1;
        while(1)
        {
            W = 0;
            int k = 0;
            for(int i = 1; i <= 6; i++)
            {
                cin >> n[i];
                W += n[i] *i;
                for(int j = 1; j <= n[i]; j = j<<1)///左移一位相当于乘2
                {
                    v[k++] = j*i;///每个的价值等于它的二进制*i
                    n[i] -= j;
                }
                if(n[i] != 0) v[k++] = n[i]*i;
            }
            if(W == 0) break;
            printf("Collection #%d:\n",t++);
            if(W % 2 != 0)///如果总重量是奇数，必定不能平分
            {
                printf("Can't be divided.\n\n");
                continue;
            }
            memset(f,0,sizeof(f));///转化成0-1背包，而且其价值=重量
            for(int i = 0; i < k; i++)
            {
                for(int j = W/2; j >= v[i]; j--)
                    f[j] = max(f[j],f[j-v[i]]+v[i]);
            }
            if(f[W/2] == W/2) printf("Can be divided.\n\n");
            else printf("Can't be divided.\n\n");
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1059]: http://acm.hdu.edu.cn/showproblem.php?pid=1059
[n_k_1_2_0_k_2_2_1_k_3_2_2_..._k_x_2_y]: https://private.codecogs.com/gif.latex?n%3Dk_%7B1%7D2%5E%7B0%7D&plus;k_%7B2%7D2%5E%7B1%7D&plus;k_%7B3%7D2%5E%7B2%7D&plus;...&plus;k_%7Bx%7D2%5E%7By%7D