## Monday, November 10, 2014

### UVa Problem 990 - Diving for Gold

Problem:

Please find the problem here.

Solution:

Knapsack, another classic problem. Instead of looking up books and implement the standard, I think about the problem again (with vague memory I had about the problem) myself, so my solution might deviate from the standard.

My idea is to have an array of achievable values, indexed by available time. To consider a treasure, either I take it, so that I achieve a bigger value with less time, or I don't. That way at the end of the program I know the biggest value achievable.

Leveraging there is only 30 treasures to consider, I used an 32 integer to represent a bitmap of which treasure is being taken associated with the value, so I can tell right away the set of taken item without backtracking pointers.

An optimization is done to make time run in 3w units - that saves time considerably.

Code:

#include "stdafx.h"

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

#include "UVa990.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>

using namespace std;

int UVa990()
{
int case_number = 0;
while (true)
{
int time_available;
cin >> time_available;
if (cin.eof())
{
break;
}
int w;
cin >> w;
int num_treasures;
cin >> num_treasures;

vector<pair<int, int> > treasures;
for (int i = 0; i < num_treasures; i++)
{
int treasure_depth;
cin >> treasure_depth;
int treasure_value;
cin >> treasure_value;
int treasure_time = treasure_depth; // in 3w units
treasures.push_back(pair<int, int>(treasure_time, treasure_value));
}

vector<int> last_values;
vector<int> last_taken;
vector<int> values;
vector<int> taken;

// Optimization - make time runs in 3w units - even a treasure of depth 1 need 3w time any way
time_available = time_available / (3 * w);
last_values.resize(time_available + 1);
last_taken.resize(time_available + 1);
values.resize(time_available + 1);
taken.resize(time_available + 1);

// Initialization - one achieve no value, however much time, if he consider no treasure
for (int t = 0; t <= time_available; t++)
{
last_values[t] = 0;
last_taken[t] = 0;
}

for (int i = 0; i < num_treasures; i++)
{
int current_treasure_time = treasures[i].first;
int current_treasure_value = treasures[i].second;

for (int t = 0; t <= time_available; t++)
{
if (t - current_treasure_time >= 0)
{
int take_value = current_treasure_value + last_values[t - current_treasure_time];
if (take_value > last_values[t])
{
values[t] = take_value;
taken[t] = last_taken[t - current_treasure_time] | (1 << i);
}
else
{
values[t] = last_values[t];
taken[t] = last_taken[t];
}
}
}

for (int t = 0; t <= time_available; t++)
{
last_values[t] = values[t];
last_taken[t] = taken[t];
}
}

if (case_number != 0)
{
cout << endl;
}
case_number++;

cout << values[time_available] << endl;
int count = 0;
for (int i = 0; i < num_treasures; i++)
{
if ((taken[time_available] & 1 << i) != 0)
{
count++;
}
}
cout << count << endl;
for (int i = 0; i < num_treasures; i++)
{
if ((taken[time_available] & 1 << i) != 0)
{
cout << treasures[i].first << " " << treasures[i].second << endl;
}
}
}

return 0;
}