Click here to Skip to main content
15,877,246 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
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++):
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;
}
Posted
Updated 6-Feb-23 8:00am
v4
Comments
Mike Hankey 5-Feb-23 10:22am    
We are willing to help but you must show an effort.
Submit what you've tried and where you are stuck.
Yor Gurt 5-Feb-23 10:34am    
Apologies, but I have not been able to produce relevant code, since I wasn't even able to devise a way of modifying the algorithm at hand to do what is desired. To be completely honest I don't want you (or anyone else) posting complete code samples. I'm just looking for some help on modifying the suggested algorithm to do what I want it to do (see the what I have tried section).

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 
Comments
Yor Gurt 5-Feb-23 17:21pm    
I have added my attempt at creating the desired algorithm to the question.
Quote:
This solution probably doesn't work, since we can't be sure that our last items will be able to cover the last fraction.

Difficult to tell if your solution works or not, without seeing your code.
As I read the requirement, It makes me think to "Linear Programming" :
Linear programming - Wikipedia[^]
 
Share this answer
 
Comments
Yor Gurt 6-Feb-23 10:30am    
Thanks for the tip, I have devised a simple algorithm, that solves for one of the parameters, would you mind giving me some advice on how I can modify it to solve for both a, and b? Regards

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900