首页 > 代码库 > zoj 1520 - Duty Free Shop

zoj 1520 - Duty Free Shop

题目:Pedro买了两块不同牌子的巧克力,他找到了一些小盒子,他准备把巧克力分开,放在小盒子里送给朋友;

           为了不被朋友发现自己是为了省钱,每个小盒子中只能放相同牌子的巧克力,求分法。

分析:dp,01背包。

           这里每个小盒子作为物品,其中第一块巧克力作为箱子,记录每个箱子的前驱(路径);

           然后,枚举所有的第一块巧克力的可分状态,判断第二块巧克力是否可以装下剩下的小盒子;

           找到合法的情况,逆序输出路径即可。

说明:当时zoj的第50道 dp O(∩_∩)O~

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

bool F[ 1001 ];
int  c[ 1001 ];
int  m[ 1001 ];

void print( int s, int d )
{
    if ( s > c[ m[ s ] ] ) {
        print( s-c[ m[ s ] ], d+1 );
        printf(" %d",m[ s ]);
    }else printf("%d %d",d,m[ s ]);
}

int main()
{
    int M,L,N;
    while ( scanf("%d%d",&M,&L) && (M+L) ) {
        scanf("%d",&N);
        int sum = 0;
        int mal = M+L;
        for ( int i = 1 ; i <= N ; ++ i ) {
            scanf("%d",&c[ i ]);
            sum += c[ i ];
        }
        
        memset( F, false, sizeof( F ) );
        F[ 0 ] = true;
        for ( int i = 1 ; i <= N ; ++ i )
        for ( int j = M ; j >= c[ i ] ; -- j )
            if ( F[ j-c[ i ] ] && !F[ j ] ) {
                F[ j ] = true;
                m[ j ] = i;
            }
        
        int space = -1;
        for ( int i = 0 ; i <= M ; ++ i )
            if ( F[ i ] && L >= sum-i ) {
                space = i;
                break;
            }
        
        if ( space != -1 ) {
            if ( space ) print( space, 1 );
            else printf("0");
        }else printf("Impossible to distribute");
        printf("\n");
    }
    return 0;
}

zoj 1520 - Duty Free Shop