Sunday, November 2, 2014

UVa Problem 11450 - Wedding shopping

Problem:

Please find the problem here.

Solution:

Goodbye greedy algorithm, hello dynamic programming. Starting this post we are going to do dynamic programming exercises, a lot of them.

For this problem, the key to our success is the relatively small amount of budget and that prices are integers. We can define opt(b, n) be the maximum amount of money within budget one can spend buying, from the 0th, to the nth type of garment, it is possible that we just can't buy anything with the current budget, and in that case we will denote opt(b, n) = -1.

Initially, n = 0, we have only 1 type of garment to buy, and the answer for this is simply a search for what is best to buy given budget.

Now suppose we already know opt(b, k) for all b and all k < K, now, to compute opt(b, K), we consider each possible garment of type K to buy, spent that money, and determine if it is feasible to buy the rest, and if it is, spend opt(b - price, K - 1). After considering each choice, pick the maximal spending and that's it. Of course, it is also possible in this case we can't buy anything and we will still represent that as -1.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2445

#include "UVa11450.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa11450()
{
    int number_of_cases;
    cin >> number_of_cases;
    for (int c = 0; c < number_of_cases; c++)
    {
        int budget;
        int num_garments_types;
        cin >> budget;
        cin >> num_garments_types;
        vector<vector<int> > garments;
        garments.resize(num_garments_types);
        for (int gt = 0; gt < num_garments_types; gt++)
        {
            int num_garments;
            cin >> num_garments;
            garments[gt].resize(num_garments);
            for (int g = 0; g < num_garments; g++)
            {
                int garment_price;
                cin >> garment_price;
                garments[gt][g] = garment_price;
            }
        }

        // Dynamic programming
        int** opt = new int*[budget + 1];
        for (int b = 0; b <= budget; b++)
        {
            opt[b] = new int[num_garments_types];
        }

        // OPT(b, 0) = the maximum price of last garment type less than or equals to b
        for (int current_budget = 0; current_budget <= budget; current_budget++)
        {
            int current_best_spent = -1; 
            for (unsigned int g = 0; g < garments[0].size(); g++)
            {
                int current_price = garments[0][g];
                if (current_price <= current_budget)
                {
                    if (current_price > current_best_spent)
                    {
                        current_best_spent = current_price;
                    }
                }
            }
            opt[current_budget][0] = current_best_spent;
        }

        // OPT(b, n) = for each affordable garment of type n, price(n) + OPT(b - price(n), n - 1)
        for (unsigned int gt = 1; gt < garments.size(); gt++)
        {
            for (int current_budget = 0; current_budget <= budget; current_budget++)
            {
                int current_best_spent = -1; 
                for (unsigned int g = 0; g < garments[gt].size(); g++)
                {
                    int current_price = garments[gt][g];
                    if (current_price <= current_budget)
                    {
                        if (opt[current_budget - current_price][gt - 1] != -1)
                        {
                            int current_spent = current_price + opt[current_budget - current_price][gt - 1];
                            if (current_spent > current_best_spent)
                            {
                                current_best_spent = current_spent;
                            }
                        }
                    }
                }
                opt[current_budget][gt] = current_best_spent;
            }
        }

        int optimal = opt[budget][num_garments_types - 1];

        if (optimal == -1)
        {
            cout << "no solution" << endl;
        }
        else
        {
            cout << optimal << endl;
        }

        for (int b = 0; b <= budget; b++)
        {
            delete[] opt[b];
        }
        delete[] opt;
    }

    return 0;
}

1 comment :