quocdat.le.insacvl's blog

By quocdat.le.insacvl, history, 5 months ago, In English

Hello everyone,

I'm currently facing an optimization problem related to server requests and would greatly appreciate your assistance. To explain the issue more clearly:

Problem Statement: We need to send multiple tickets to a server, and our goal is to minimize the number of requests made.

Here's an example to illustrate the problem:

Request	Amount
1+3	2
1+2	1
1+4	3
2+3	4
2+4	1
2+5	2
3+4	1
3+5	2
3+6	5

In this example, each request combines specific tickets with corresponding amounts. For instance, the first request (1+3) means we are attempting to send ticket 1 and ticket 3, with a total amount of 2 for each.

We have two methods to reduce the number of requests:

1. Banker Method:

Combine multiple requests into one request. For example, 1>2,3,4,5 corresponds to sending (1+2), (1+3), (1+4), (1+5).

2. Permutation Method:

Send all possible pairs of tickets as one request. For example, 1+2+3+4 corresponds to sending (1,2), (1,3), ... (3,4). In the example provided, here's one possible solution:

Request	Amount
1>2,3,4	1
1>3,4	1
2>3,5	2
3>5,6	2
1+4	1
2+3+4	1
3+6	3
2+3	1

This solution achieves the same total amount, preserves the amount of each ticket, and uses only 8 requests instead of 9.

However, I'm seeking the optimal solution, which in this case is:

Request	Amount
3>1,2,5,6	1
3>1,2,4,5	1
1+2+3+4+6	1
2+3+5	1

I've attempted a greedy solution using graphs and also explored a constraint-satisfaction approach, but neither has provided the optimal solution. I believe dynamic programming might hold the key, but I'm uncertain about how to think and implement it.

If you have any ideas or insights to help solve this challenge, please share them with me. Your assistance is greatly appreciated.

For more details, the constraint is relatively small. 1<= Ticket <=10. Number of initial requests <=30. Amount <= 1k.

Thank you very much for your support.

Full text and comments »

By quocdat.le.insacvl, history, 2 years ago, In English

Hi Everyone,

I’m elated to have found this awesome roadmap written by YouKn0wWho.

Then, I takes my time to make a markdown-checklist from this problemset to track my progress. You can see it here.

I hope it could be helpful for someone...

Thank you!

Full text and comments »