HDU 1059 Dividing（多重背包）

题意：将大理石的重量分为六个等级，每个等级所在的数字代表这个等级的大理石的数量，如果是0说明这个重量的大理石没有。将其按重量分成两份，看能否分成。

思路：一开始以为是简单的01背包，结果写出来之后不对，因为以为从头开始往上加就行了，看能不能满足那个标准，后开才反应过来，还可以跳着加呢，让YN美女给我讲了一下，然后不小心手残了一下交了两遍WA之后终于AC了，其实就是用一个数组c来标记状态，c[i]表示 i 这个重量是可以用目前的石头表示出来的。而b数组表示的是这种石头的使用次数，也代表着用了几个了。

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std ;

int a[10] ;
int b[146565] ;
int c[242124] ;

int main()
{
    int casee = 0 ;
    while(1)
    {
        int sum = 0 ;
        for(int i = 1 ; i <= 6 ; i++)
        {
            scanf("%d",&a[i]) ;
            sum += a[i] * i ;
        }
        if(sum == 0) break ;
        printf("%d*\n",sum) ;
        casee++ ;
        if(sum % 2 != 0)
        {
            printf("Collection #%d:\nCan't be divided.\n\n",casee) ;
            continue ;
        }
        else
        {
            sum = sum / 2 ;
            memset(c,0,sizeof(c)) ;
            c[0] = 1 ;
            for(int i = 1 ; i <= 6 ; i++)
            {
                if(a[i] > 0)
                {
                    //continue ;
                    memset(b,0,sizeof(b)) ;
                    for(int j = i ; j <= sum ; j++)//因为这个石头的重量是i，所以从i开始枚举
                    {
                        if(c[j-i] && !c[j] && b[j-i] < a[i])//j-i这个重量是可以表示出来的，但是j这个重量还没表示，但是因为重量是i，所以既然j-i可达，那j肯定也可达
                        {
                            c[j] = 1 ;
                            b[j] = b[j-i]+1 ;//表示了一次，就代表价值为i的这些石头用过一块了
                        }
                    }
                }

            }
            if(c[sum])
                printf("Collection #%d:\nCan be divided.\n\n",casee) ;
            else
                printf("Collection #%d:\nCan't be divided.\n\n",casee) ;
        }

    }
    return 0 ;
}

View Code

HDU 1059 Dividing（多重背包）

推荐阅读