Печать страницы - TraditionalMarriage

TraditionalMarriage
Традиционная свадьба (Уровень2).
оригинал тут (http://www.topcoder.com/stat?c=problem_statement&pm=8260&rd=10792)

Очки за задачу: 500
Кол-во присланных решений / кол-во участников 48 / 73 (65.75%)
Количество решений прошедших все тесты / общее количество решений 19 / 48 (39,58%)

Постановка задачи:
Люси всегда мечтала устроить большую традиционную свадьбу. Прямо сейчас она сидит на кровати и перебирает все свои вещи стафф. У нее в голове только одна мысль: «Надо выбрать что-то традиционное (old), что-то новенькое модное (new), что-то занять у подруг (borrowed) и что-то голубое (blu)». За несколько часов она составила список всех своих вещей и при том указала их вес. Она хочет выбрать такие вещи, чтобы они удовлетворяли всем требованиям и общий их вес был минимален. Помогите ей!

Выполучите массив строк, описание вещей, String[], и массив чисел int[] с весом вещей.
properties[ i ] - список свойств i-ой вещи, разделенный запятыми,
weight[ i ] - вес i-ой вещи.

Вы должны выбрать из списка вещи, удовлетворяющие двум условиям
-Как минимум 1 вещь должна быть «new», Как минимум 1 вещь должна быть «old», Как минимум 1 вещь должна быть «borrowed», Как минимум 1 вещь должна быть «blue»
- общий их вес вещей должен быть минимален.

Выведите вес выбранных вами вещей. Если нет никаких вариантов, то вывести -1.

Ограничения:
- каждая вещь может содержать до 50 свойств.
-свойства и вес вещей расположены под одним индексом.
-каждое свойство вещи размером от 1 до 50 символов.
-список свойств разделен запятыми и состоит из цифр 0-9 и букв ('a'-'z') в маленьком регистре.
-у каждой вещи нет повторяющихся свойстви каждая вещь имеет хотя-бы 1 свойство.
-каждая вещь имеет вес от1 до 10^6.

Примеры:

{"blue,suede,old","red","white,borrowed","new,white,cool,good,anything","new"}
{10,4,15,3,4}
Ответ: 28
Люси должна взять 1 и 3 вещь. Чтобы взять что-то "new" она может выбрать или 4 или 5. Но для минимизации веса она выберет 4.

{"new,borrowed,blue,old,nice"}
{1}
Ответ: 1

{"old","new","borrowed","blue","old,new,borrowed,blue"}
{1,1,1,1,5}
Ответ: 4
Лучше взять первык 4 вещи чем 1 пятую.

{"new","old,red","borrowed"}
{1,2,3}
Ответ: -1
Нет ни одной вещи со свойством "blue".

Решение:
Давайте отметим, что максимальное кол-во вещей которое может нам понадобится это 4.
Пусть у нас есть n вещей. Общее количество различный переборов в худшем случае будет:
C(n,1) + C(n,2) + C(n,3) + C(n,4).

Для n = 50 это составит 251175 вариантов.
Где C(n.k) биноминальный коэффициент (k выборов из n).
Таким образом нам необходимо проверить все эти варианты, чтобы найти решение с минимальным весом.

Рассмотрим решение (http://www.topcoder.com/tc?module=HSProblemSolution&cr=11972352&rd=10792&pm=8260) кодера Zuza's (http://www.topcoder.com/tc?module=MemberProfile&cr=11972352&tab=alg).

Код: (cpp)

#include <algorithm>
#include <functional>

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <string>
#include <sstream>
#include <iostream>

using namespace std;

#define FORC(it,v) for( __typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it )

struct item {
    int w;
    int s;

    item( int _state, int _w ) : w( _w ), s( _state ) {}
};

class TraditionalMarriage {
public:
    int getLuckyItems( vector <string> properties, vector <int> weight ) {
        vector< item > V;
        
        for( int i = 0; i < ( int )properties.size(); ++i ) {
            FORC( it, properties[i] ) if( *it == ',' ) *it = ' ';
            istringstream in( properties[i] );

            int s = 0;

            for( string x; in >> x; ) {
                if( x == "blue" ) s |= 1;
                if( x == "new" ) s |= 2;
                if( x == "old" ) s |= 4;
                if( x == "borrowed" ) s |= 8;
            }

            V.push_back( item( s, weight[i] ) );
        }

        int mini = 1000000000;
        int n = V.size();

        for( int a = 0; a < n; ++a )
            if( V[a].s == 15 )
                mini <?= V[a].w;

        for( int a = 0; a < n; ++a )
            for( int b = 0; b < n; ++b )
                if( (V[a].s|V[b].s) == 15 )
                    mini <?= V[a].w + V[b].w;


        for( int a = 0; a < n; ++a )
            for( int b = 0; b < n; ++b )
                for( int c = 0; c < n; ++c )
                    if( (V[a].s|V[b].s|V[c].s) == 15 )
                        mini <?= V[a].w + V[b].w + V[c].w;

        for( int a = 0; a < n; ++a )
            for( int b = 0; b < n; ++b )
                for( int c = 0; c < n; ++c )
                    for( int d = 0; d < n; ++d )
                        if( (V[a].s|V[b].s|V[c].s|V[d].s) == 15 )
                            mini <?= V[a].w + V[b].w + V[c].w + V[d].w;

        if( mini == 1000000000 ) return -1;

        return mini;
    }
};

КИТА unofficial

Ваши интересы => Задачи с TopCoder => Тема начата: vimmax от Ноябрь 21, 2007, 08:35:56