We have n item types, each item type has 3 properties:
price
,
a
,
b
:
{ price: 4.0, a: 12.0, b: 12.0 }
{ price: 1.0, a: 2.0 , b: 4.0 }
{ price: 0.5, a: 1.5 , b: 0.5 }
We also have two global
a
and
b
values:
a: 5.0
b: 7.0
We need to find a combination of our item types that
exactly matches our global
a
and
b
values, and at the lowest possible price.
Example solution:
An example solution for the above example is as follows:
0.25 * { price: 4.0, a: 12.0, b: 12.0 }
1.0 * { price: 1.0, a: 2.0 , b: 4.0 }
------------------------------------------
price = 2.0 (0.25 * 4.0 + 1.0 * 2.0)
a = 5.0 (0.25 * 12.0 + 1.0 * 2.0)
b = 7.0 (0.25 * 12.0 + 1.0 * 4.0)
Limitations:
- our item stock is infinite
- we may use fractions of items
- we have an unlimited amount of money, but we should use as little as possible
What I have tried:
I have tried implementing a fractional knapsack solver, but have failed to do so.
After some thought I have devised the following algorithm:
We go through all the item types, and calculate an efficiency ratio (something along the lines of price / a / b). We then sort our item types using this ratio. We then start adding item types together, adding a's and b's in the process. After we can no longer add our item types together (probably for the last item) we start using fractions.
This solution probably doesn't work, since we can't be sure that our last items will be able to cover the last fraction.
Code for A only (c++):
#include <iostream>
#include <algorithm>
#include <vector>
struct item {
double price;
double a;
double b;
};
static bool cmp(item a, item b)
{
double r1 = a.price / a.a;
double r2 = b.price / b.a;
return r1 > r2;
}
int main() {
double a_req = 7.0;
double b_req = 5.0;
std::vector<item> items{
{ 4.0, 12.0, 12.0 },
{ 1.0, 2.0, 4.0 },
{ 0.5, 1.5, 0.5 }
};
std::sort(items.begin(), items.end(), cmp);
double price = 0.0;
for (int i = 0; i < items.size(); i++) {
if (items[i].a <= b_req) {
b_req -= items[i].a;
price += items[i].price;
std::cout << "1 * " << i << '\n';
}
else {
double ratio = b_req / items[i].a;
price += items[i].price * ratio;
std::cout << ratio << " * " << i << '\n';
break;
}
}
return 0;
}