Equal Gifts Algorithm Problem

4

Collegamento problema - link

It is Lavanya's birthday and several families have been invited for the birthday party. As is customary, all of them have brought gifts for Lavanya as well as her brother Nikhil. Since their friends are all of the erudite kind, everyone has brought a pair of books. Unfortunately, the gift givers did not clearly indicate which book in the pair is for Lavanya and which one is for Nikhil. Now it is up to their father to divide up these books between them.

He has decided that from each of these pairs, one book will go to Lavanya and one to Nikhil. Moreover, since Nikhil is quite a keen observer of the value of gifts, the books have to be divided in such a manner that the total value of the books for Lavanya is as close as possible to total value of the books for Nikhil. Since Lavanya and Nikhil are kids, no book that has been gifted will have a value higher than 300 Rupees...

Per il problema, non ho potuto pensare ad altro che alla ricorsione. Il codice che ho scritto è riportato di seguito. Ma il problema è che il codice è inefficiente nel tempo e fornisce TLE (limite di tempo superato) per 9 casi di test su 10! Quale sarebbe un approccio migliore al problema?

Codice -

#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;

int n,g[150][2];

int diff(int a,int b,int f) {
    ++f;
    if(f==n) {
               if(a>b) {
                       return a-b;
               }
               else {
                    return b-a;
               }
    }
    return min(diff(a+g[f][0],b+g[f][1],f),diff(a+g[f][1],b+g[f][0],f));
}

int main() {
    int i;
    scanf("%d",&n);
    for(i=0;i<n;++i) {
                     scanf("%d%d",&g[i][0],&g[i][1]);
    }
    printf("%d",diff(g[0][0],g[0][1],0));
}

Nota - È solo una domanda di pratica, & non fa parte di una competizione.

    
posta 7Aces 31.10.2012 - 13:07
fonte

3 risposte

7

Faccio appena capolino prima della riunione dello stato del mattino:

Sort books descending by value
Give first book to Lavanya
while books remain
    while Nikhil's values < Lavanya's values
        Give first book to Nikhil
    while Lavanya's values < Nikhil's values
        Give first book to Lavanya

Lo farà?

    
risposta data 31.10.2012 - 13:41
fonte
1

Sembra che ci sia una certa confusione riguardo al mio commento sulla risposta di Ben, quindi ecco la mia soluzione indipendente:

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stdlib.h>
using namespace std;

typedef pair<int, int> BookPair;
typedef vector<BookPair*> BookList;

void readBookList(BookList &books)
{
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        int cheapBook = min(a, b);
        int expensiveBook = max(a, b);
        BookPair *bookPair = new BookPair(cheapBook, expensiveBook);
        books.push_back(bookPair);
    }
}

bool diffsort(BookPair *p1, BookPair *p2)
{
    return abs(p1->first - p1->second) > abs(p2->first - p2->second);
}

void allocate(BookList &books)
{
    int lavanya = 0;
    int nikhil = 0;

    for (BookList::iterator it = books.begin(); it != books.end(); ++it)
    {
        int cheapBook     = (*it)->first;
        int expensiveBook = (*it)->second;

        if (lavanya < nikhil)
        {
            lavanya += expensiveBook;
            nikhil += cheapBook;
        }
        else
        {
            nikhil += expensiveBook;
            lavanya += cheapBook;
        }
    }

    cout << abs(lavanya - nikhil) << endl;
}

int main(int argc, char* argv[])
{
    BookList books;

    readBookList(books);
    sort(books.begin(), books.end(), diffsort);
    allocate(books);

    return 0;
}

Fondamentalmente, si ordinano le coppie di libri in base alla differenza di prezzo tra loro, prima la differenza maggiore. (1, 3) andrebbe prima (300, 300). Poi assegni i libri una coppia alla volta, dando al bambino il libro più economico il cui precedente ammontare è più costoso.

Si ordina in base alla differenza anziché al valore assoluto del libro, perché la differenza è ciò che si sta tentando di equalizzare. Ciò evita problemi con insiemi come (1, 201) (150, 300), (150.300). L'assegnazione più equa è che un bambino ottenga entrambi i libri da 300 rupie e il libro da 1 rupia. Questo dà loro solo 100 rupie in più rispetto all'altro bambino.

Se si ordina invece per il valore assoluto più grande, ogni bambino riceverà un libro da 300 rupie, ma un bambino finirà con altre 200 rupie rispetto all'altro bambino.

    
risposta data 31.10.2012 - 18:37
fonte
1

Kevin Cline lo ha già detto, ma ha cancellato la sua risposta, quindi ripeterò e spiegherò: Questo problema è un problema con lo zaino. Ogni coppia di libri può essere rappresentata dalla differenza di prezzo di questi due libri. Queste differenze di prezzo dovrebbero essere equamente distribuite, il che equivale a trovare un sottoinsieme delle differenze di prezzo di cui la somma è la metà della somma totale di tutte le differenze di prezzo.

Esempio:

Pair   Book1   Book2  Difference
1      100     60     40
2      90      40     50
3      70      50     20
4      65      55     10

Esaminando il set di differenze, {40,50,20,10} , il totale è 40 + 20 + 50 + 10 = 120 , quindi cerchiamo un sottoinsieme con una somma vicina o uguale a 120/2 = 60 . Usando uno degli algoritmi esistenti per il problema dello zaino, otteniamo ad es. {50,10}. Questo sottoinsieme può essere ricondotto alle coppie, quindi un bambino ottiene il libro più costoso delle coppie 2 e 4, mentre l'altro bambino ottiene il libro più costoso delle coppie 1 e 3.

Il link spiega gli algoritmi per l'approssimazione della soluzione dei problemi dello zaino.

    
risposta data 07.11.2012 - 13:03
fonte

Leggi altre domande sui tag