اصغر پرنده به یک عروسی دعوت شده است. در هنگام شام n n نوع غذا روی میز قرار دارند که به…
- User
اصغر پرنده به یک عروسی دعوت شده است. در هنگام شام n n نوع غذا روی میز قرار دارند که به ترتیب از ۱ تا n n شماره گذاری شده اند. خانواده داماد که بسیار خسیس هستند از مهمان ها بابت شام پول میگیرند.
تعداد واحد های موجود از غذای i iام L i L i ، و قیمت هر واحد از آن برابر با C i C i است. هربار که یک مهمان بشقابی برمیدارد، باید از غذای شماره ۱ تا غذای شماره p p حرکت کند و یک واحد از هر غذایی که تمام نشده بود بردارد و در نهایت C p C p دلار پول بپردازد. این کار را در صورتی میتوان انجام داد که از غذای p pام حداقل یک واحد موجود باشد.
اصغر گشنه است، قیمت دلار بالا رفته و جمع پول هایی که در جیب و جورابش پنهان کرده روی هم k k دلار است. او میخواهد این پول را به طوری خرج کند که جمع قیمت غذاهایی که میخورد بیشینه شود. این مقدار بیشینه را به دست آورید.
ورودی در خط اول ورودی دو عدد n n و k k آمده اند.
در خط دوم، n n عدد که i iامین آنها C i C i است، و در خط بعدی هم n n عدد که i iامینشان برابر با L i L i است آمده اند.
1 ≤ n ≤ 40 1≤n≤40 1 ≤ k ≤ 64
000 1≤k≤64 000 1 ≤ C i ≤ 40 1≤C i ≤40 0 ≤ L i ≤ 40 0≤L i ≤40
خروجی خروجی برنامه تنها یک عدد است که برابر با بیشینه مقدار مجموع قیمت غذاهاست.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۰۰ بدون محدودیت اضافی مثال ورودی نمونه 6 8 7 2 3 5 7 2 1 3 0 3 2 1 Plain text خروجی نمونه 30 Plain text ابتدا از غذای ۱ تا ۶ میرویم و در طول راه از غذاهای نوع ۱، ۲، ۴، ۵ و ۶ هرکدام یک واحد برمیداریم (از غذای نوع ۳ نمیتوان برداشت چون تعدادش ۰ است).
در مرحله بعد از غذای ۱ تا ۴ میرویم غذا های نوع ۲ و ۴ را برمیداریم.
در مرحله اول ۲ دلار و در مرحله دوم ۵ دلار هزینه کرده ایم که از پولمان که برابر با ۸ است کمتر است.
مجموع قیمت غذاها در مرحله اول برابر با ۲۳ و در مرحله دوم برابر با ۷ است.
c++
- Assistant
The problem can be effectively formulated as an Integer Linear Programming (ILP) model, which can be solved using an ILP solver.
Variables: Let ( x_p ) be the number of times Asghar performs operation ( p ) (i.e., goes from food ( 1 ) to food ( p ), pays ( C_p ) dollars, and takes one unit from each non-exhausted food from ( 1 ) to ( p )).
Constraints:
-
Food Capacity Constraints: For each food ( i ) (from ( 1 ) to ( n )): [ \sum_{p=i}^{n} x_p \leq L_i ] This ensures that the total units collected from each food ( i ) do not exceed its capacity ( L_i ).
-
Total Cost Constraint: [ \sum_{p=1}^{n} C_p \cdot x_p \leq k ] This ensures that the total cost does not exceed Asghar's available money ( k ).
Objective Function: Maximize the total value collected: [ \text{Maximize } Z = \sum_{p=1}^{n} x_p \cdot \left( \sum_{i=1}^{p} C_i \right) ] This computes the total value of the food collected, considering that in each operation ( p ), Asghar collects one unit of each available food from ( 1 ) to ( p ), each valued at ( C_i ).
Solution Approach:
-
Model the Problem as ILP:
- Define variables ( x_p ) for ( p = 1 ) to ( n ), integers between ( 0 ) and ( L_p ).
- Set up the constraints as detailed above.
- Define the objective function to maximize total value.
-
Use an ILP Solver:
- Utilize an ILP solver such as GLPK, CBC, or any other solver that can handle integer variables.
- Input the model into the solver and run it to find the optimal values of ( x_p ).
-
Compute the Total Value:
- Once the optimal ( x_p ) values are obtained, compute the total value based on the objective function.
Implementation in C++:
#include <iostream> #include <vector> #include <cstdio> #include <ilcplex/ilocplex.h> int main() { int n; long long k; std::cin >> n >> k; std::vector<int> Ci(n), Li(n); for (int i = 0; i < n; ++i) { std::cin >> Ci[i]; } for (int i = 0; i < n; ++i) { std::cin >> Li[i]; } IloEnv env; try { IloModel model(env); IloIntVarArray x(env, n, 0, IloIntMax); for (int i = 0; i < n; ++i) { x[i] = IloIntVar(env, 0, Li[i]); } // Food capacity constraints for (int i = 0; i < n; ++i) { IloExpr sum(env); for (int p = i; p < n; ++p) { sum += x[p]; } model.add(sum <= Li[i]); sum.end(); } // Total cost constraint IloExpr totalCost(env); for (int p = 0; p < n; ++p) { totalCost += x[p] * Ci[p]; } model.add(totalCost <= k); totalCost.end(); // Objective function IloExpr totalValue(env); for (int p = 0; p < n; ++p) { IloExpr sumCi(env); for (int i = 0; i <= p; ++i) { sumCi += Ci[i]; } totalValue += x[p] * sumCi; sumCi.end(); } IloObjective obj = IloMaximize(env, totalValue); model.add(obj); totalValue.end(); IloCplex cplex(model); cplex.solve(); IloNum optimalValue = cplex.getObjValue(); std::cout << (long long)optimalValue << std::endl; } catch (IloException& e) { std::cerr << "Concert exception: " << e << std::endl; } catch (...) { std::cerr << "Unknown exception." << std::endl; } env.end(); return 0; }Explanation:
- We use the IBM CPLEX optimizer library (you can use any ILP solver you have access to).
- Variables ( x_p ) are created for each operation ( p ), constrained between ( 0 ) and ( L_p ).
- Constraints are added to ensure the number of units collected from each food does not exceed its capacity, and the total cost does not exceed ( k ).
- The objective function is set to maximize the total value collected.
- The ILP is solved, and the optimal total value is printed.
Note:
- You need to have an ILP solver and its C++ API installed and properly configured for this code to compile and run.
- Ensure that the integer variables and coefficients are within the range that the solver can handle.
Final Answer:
An optimal total value can be computed by formulating an integer linear programming model with variables ( x_p ) (number of times operation ( p ) is performed), applying the food capacity and total cost constraints, and maximizing the total value collected, then solving the model using an ILP solver.
-