2016年5月18日 星期三

UVA 11450 Wedding shopping (講解fill)

/*    
    題目連結

    很經典的背包問題
    要注意的是 每種衣物要"恰好"買一項

    另外 fill(*l,*r,num)的功能
    在於把 所有在l和r之間的變數 (左閉右開)
    全部設成 num 
*/
#include <iostream>
#include <cstdio>

using namespace std;

bool *DP1 = new bool[201];
bool *DP2 = new bool[201];

int main()
{
    int N;
    scanf("%d", &N);

    while( N-- )
    {
        int M, C;
        scanf("%d %d", &M, &C);

        fill(DP1, DP1+M+1, false);
        DP1[0] = true;

        for(int Ci = 0; Ci < C; Ci++)
        {
            fill(DP2, DP2+M+1, false);

            int K;
            scanf("%d", &K);

            for(int Ki = 0; Ki < K; Ki++)
            {
                int price;
                scanf("%d", &price);

                for(int Mi = price; Mi <= M; Mi++)
                    DP2[Mi] |= DP1[Mi-price];
            }

            swap(DP1, DP2);
        }

        int ans = -1;

        for(int Mi = M; Mi >= 0; Mi--)
            if( DP1[Mi] )
            {
                ans = Mi;
                break;
            }

        if( ans != -1 ) printf("%d\n", ans);
        else puts("no solution");
    }
}

沒有留言:

張貼留言