Sale Problem

sale.cpp

//Rikaard Hosein
//811004653

#include <cstdlib>
#include <cstdio>
#include <climits>
#include <memory.h>
using namespace std;

#define _DEBUG_

#define MAX_ITEMS 5
#define MAX_OFFERS 99+5


unsigned int num_items;  // 0 <= num_items <= 5
unsigned int num_special_offers;
unsigned int num_offers;

unsigned int desired_items[MAX_ITEMS];
unsigned int desired_quantities[MAX_ITEMS];

struct Offer
{
    unsigned int items[MAX_ITEMS];
    unsigned int quantity[MAX_ITEMS];
    unsigned int num_items;
    unsigned int price;
};

Offer offers[MAX_OFFERS];

unsigned int memoize_array[6][6][6][6][6];


//quantities is modified
bool offer_appropriate( unsigned int *items, unsigned int num_items,
unsigned int *quantities, Offer offer )
{
    //For an offer to be considered appropriate, it must contain a subset
    //of the items in the list of desired items and the quantities must be
    //less than or equal to the quantities in the list of desired items.
    unsigned int i,j;
    
    for( i = 0; i < offer.num_items; ++i )
    {
        bool found = false;
        //is item found in the desired list of items
        for( j = 0; j < num_items; ++j )
        {
            if( offer.items[i] == items[j] )
            {
                found = true;
                break;
            }
        }
        
        if( !found ) return false;
        //Item was found, check quantity
        if( offer.quantity[i] > quantities[j] ) return false;
        else
        {
            quantities[j] -= offer.quantity[i];
        }
    }
    
    //If all items were found in the desired list of items
    //and their quantities were less than or equal to the quantities
    //requred, then return true.
    return true;
}



unsigned int minimum_price( unsigned int *items, unsigned int num_items, unsigned int *quantities )
{
    bool finished = true;
    for( unsigned int i = 0; i < num_items; ++i )
    {
        if(quantities[i])
        {
            finished = false;
            break;
        }
    }
    
    if( finished ) return 0;
    
    //ADD MEMOIZATION
    unsigned int x;
    if( x = memoize_array[quantities[0]][quantities[1]][quantities[2]][quantities[3]][quantities[4]] )
    return x;
    
    
    unsigned int min_price = UINT_MAX;
    
    for( unsigned int i = 0; i < num_offers; ++i )
    {
        //need to duplicate original quantity array since it might be modified
        unsigned int temp_quantities[MAX_ITEMS];
        memset( &temp_quantities, 0, MAX_ITEMS*sizeof(unsigned int) );
        for( unsigned int j = 0; j < num_items; ++j )
        temp_quantities[j] = quantities[j];
        
        //Can this offer be used?
        bool appropriate = offer_appropriate( items, num_items, temp_quantities, offers[i] );
        if( !appropriate ) continue;
        
        unsigned int temp_price = offers[i].price + minimum_price( items,num_items,temp_quantities );
        
        if( temp_price < min_price ) min_price = temp_price;
        
    }
    
    
    memoize_array[quantities[0]][quantities[1]][quantities[2]][quantities[3]][quantities[4]] = min_price;
    return min_price;
}




int main()
{
    FILE *input = fopen("input.txt","r");
    
    //These is the list of desired items
    fscanf(input,"%u",&num_items);
    for( unsigned int i = 0; i < num_items; ++i )
    {
        offers[i].num_items = 1;
        offers[i].quantity[0] = 1;
        unsigned int quantity;
        fscanf( input, "%u %u %u", &offers[i].items[0], &quantity, &offers[i].price  );
        
        ++num_offers;
        
        desired_items[i] = offers[i].items[0];
        desired_quantities[i] = quantity;
    }
    
    
    fscanf(input,"%u",&num_special_offers);
    
    for( unsigned int i = 0; i < num_special_offers; ++i )
    {
        unsigned int temp_num_items;
        fscanf(input,"%u",&temp_num_items);
        
        offers[num_offers].num_items = temp_num_items;
        
        for( unsigned int j = 0; j < temp_num_items; ++j )
        fscanf( input, "%u %u", &offers[num_offers].items[j], &offers[num_offers].quantity[j] );
        
        fscanf( input, "%u", &offers[num_offers].price );
        ++num_offers;
    }
    
    fclose(input);
    
    
    unsigned int min_price = minimum_price( desired_items, num_items, desired_quantities );
    
    
    FILE *output = fopen("output.txt","w");
    fprintf(output,"%u",min_price);
    fclose(output);
}