#Dynamic programming problem that i need help with ;-;

62 messages · Page 1 of 1 (latest)

tidal tuskBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

mossy atlas
#

im assuming you've given it a crack?

versed granite
#

yeah i have tried to solve it in a dynamic way but i think my logic is just wrong

#

that's i am here, maybe it has another method of solution

#

i am basically looking for a "starting" point

mossy atlas
#

Well to maximize profit, your program should first identify the highest apple prices in each city over the given number of days, N. Then, it should compare the prices and determine which city has the highest price.

#

Then you should calculate the time it takes to travel to that city and back to Provins, and subtract that time from the day on which the highest price is found. This will be the day on which the apples should be sold.

versed granite
#

also i think i should mention this but the real test cases are n < 100 000

mossy atlas
#

You can loop through the list of tuples and use variables to keep track of the highest prices in each city and the corresponding day, then use if-else statements to compare the highest prices and determine the optimal city to sell in.

versed granite
#

but that doesn't work because the price for day 1 is 1000 in lille, and it takes 3 days to drive to lille, so when we reach lille on day 3, the highest price would have 300

clever tartan
#

There might be a way to use A-star.

versed granite
#

so basically think of this as a sort of graph and find the most costly path?

clever tartan
#

It's my first idea. Sounds plausible to me.

#

The heuristic can be the sum of leftover days of both cities, but there is probably a better one.

#

The potential ways are "stay" and "move to [places]".

versed granite
#

hmmm

#

if you were to make a sort of pseudocode for it, what would it be?

#

just so i can hear your thought process

clever tartan
# 
struct State {
  enum class Position { Paris, Lile, Province} position;
  int apples;
  int money;
  int day;
  int potential; //heuristic estimating best possible money from here
};

std::priority_queue<State> options; //sort by potential

void astar() {
  for (auto option = options.top(); option.potential != option.money; option = options.top()) {
  options.pop();
  auto staying_option = option;
  staying_option.apples - sold_apples;
  staying_option.money += money; //look up from given list
  potential = heuristic();
  options.push(staying_option);
  if (option.location == State::Position::Province) {
    auto paris_option = ...;
    options.push(paris_option);
  }
  //lille_option
  //province_option
}
#

Oh yeah, you need to start with options.push({State::Position::Province, max_apples, 0, 0, heuristic()});.

versed granite
#

a question what is the expected code to be replaced with lille_option and province_option?

clever tartan
#

Same as paris_option. First you need to check if you can even get to Paris from option.position. Then you need to modify day and apples accordingly.

#

And finally call your heuristic function to calculate the potential.

versed granite
#

hmmmm

#

alright, i'll try to write a code based on your pseudocode and methods

clever tartan
#

The better your heuristic, the faster it will find a solution. If your heuristic is garbage (like a constant) it'll be extremely slow.

versed granite
#

what is a heuristic you recommend?

clever tartan
#

I haven't thought of a good one. You want the heuristic to spit out a low as possible value, but it can't be wrong.

#

I haven't understood how many apples you can carry.

#

It seems like you can only carry 1 pack, so int apples is not correct, bool has_apples is better.

#

Actually wait, this makes it a bit easier.

versed granite
#

yeah your car has space for one batch, and you sell the entire batch and you get the entire money for that batch

clever tartan
#

You could say State is always in Province with has_apples == true. So you can remove has_apples and position. So every step in the algorithm is "Go to [city], wait [days], sell, drive back and restock".

versed granite
#

but one thing, the problem remains the same, cause what i am trying to find is a program that finds the best potential for everyday and every price

clever tartan
#

It doesn't make sense to wait more than 4/6 days, because in that time you can go back, so the number of options you add are limited.

versed granite
#

yeah

clever tartan
#

If you need the actual route and not just the best sell price you can give State a vector<std::pair<Position, int>> member for where you go and how long you stay or something.

versed granite
#

wait, then what is the heuristic?

clever tartan
#

The heuristic estimates the potential and is what the queue sorts on. It's what A-star uses to figure out the most promising option.

#

I'd use the number of days left, take the max of sell price from Lille and Paris and divide by 4 as the first heuristic.

#

With a little luck it's already good enough.

#

Like with

Lille, Paris
100, 100
1000, 1000
350, 300
200, 400
100, 100
300, 300
and 3 days left it would be max(200, 400) + max(100, 100), max(300, 300) / 4.

#

Actually the heuristic only really needs the days left as input, so you can calculate the potentials for all days once and then just refer to the list.

versed granite
#

@clever tartan okay so after an hour of headache, i made this program, i have tried to implement the things you talked about but the code doesn't work. Could you take a look at it and tell me what you think?

📎 apple.cpp
clever tartan
#

Can you be more precise than "code doesn't work"?

#

I don't understand some parts. For example what is this for?

    if (curr.position != Provins) {
      State next;
      next.day = curr.day + 1;
      next.apples = curr.apples;
      next.money = curr.money + Input[next.day][next.position];
      if (is_feasible(next)) {
        next.heuristic = heuristic(next);
        pq.push(next);
      }
    }

You're handling the situation when you're not in the province and calculating the next state. A day passes, the apples stay the same, money gets added. This is not how the rules go. If the apples get sold they are gone.

# 
    for (int i = 0; i < 2; i++) {
      State next;
      next.position = i;
      next.day = curr.day;
      next.apples = curr.apples + 1;
      next.money = curr.money;
      if (is_feasible(next)) {
        next.heuristic = heuristic(next);
        pq.push(next);
      }
    }

This one is even stranger. You are iterating over something, but don't use proper types, so it's difficult to read. I think i is the positions, but I'm not entirely sure. So you go through the places, the day does not change. That's wrong, there is travel time involved in changing the place. Also you cannot travel directly from Paris to Lille which you don't check for. Also you cannot restock in every place, only in the province. Also the apples don't get added on, either you have apples or you don't.

versed granite
#

@clever tartan i tried to complete your pseudo-code then i used chatgpt to make an equivalent c++ code for it

clever tartan
#

I don't know what to tell you. Normally I would try to show you how to do it, but I don't know how to get ChatGPT to do it.

versed granite
#

but if it is possible for you, could you give me like a pseudocode that does the things you said

#

like one that is a bit more completed

clever tartan
#

I don't want to keep changing the pseudo code until chatgpt spits out correct C++. That's way too much effort.

versed granite
#

oh, then would it be possible for you to write a c++ code?

clever tartan
#

Sure, but that goes against everything here. The point is to teach you C++. If you're not interested in that I guess you'll just have to hire someone or ask other people.

versed granite
#

I mean i am up for learning it if you have the time/patience ;-;

clever tartan
#

You have the core code already. There are just some details wrong, and you don't even need to know C++ to fix them.

#

Specifically the parts I pointed out.

versed granite