#ifndef __MENU_H
#define __MENU_H
#include <vector>
using std::vector;
// We are solving the problem of the "least expensive menu".
// Like what's written on the side of breakfast cereal boxes, we look at the
// nutritional values of each of our ingredients: calories, proteins, lipids,
// vitamins, etc.
//
// We know the daily recommended amounts of each of these "elements" (element =
// vitamin, etc). We call them "DRA" (Daily Recommended Amount), and it is given
// in the "dra" array.
// For example, if one needs at least 2000 calories, 60g of protein, etc per day,
// we'll get dra = [2000, 60, ...].
//
// We also have the list of all possible ingredients: potatoes, rice,
// orange juice, chicken, etc.
// We know the nutrional values of each ingredient in all elements: calories,
// etc (for 1kg of this ingredient). For ingredient #i those values will be in
// nutri_values_per_ingredient[i], in the same order as the "dra" array.
// For example, say 1kg of potatoes amounts to 2500 calories, 10g of proteines,
// etc; 1kg of rice amounts to 4000 calories, 13g of proteins, etc; and so on
// for all other ingredients. "nutri_values_per_ingredient" would then be:
// [[2500, 10, ...], // 1kg of potatoes
// [4000, 13, ...], // 1kg of rice
// ... ] // .. other ingredients ..
//
// Finally, the price (per kg) of each ingredient is in "price_per_ingredient".
// Ingredients are listed in the same order as in "nutri_values_per_ingredient".
// For example, if 1kg of potatoes costs $3.2, 1kg of rice costs $5.4, etc,
// then price_per_ingredient = [3.2, 5.4, ...].
//
// The goal is to find the cheapest possible menu that covers *at least* the
// DRA. I.e. we must find which ingredients to buy, and what quantity. It's ok
// if we have too much of a given element (e.g. too much vitamin), it doesn't
// matter. We only need to be ≥ DRA.
//
// This function must find this cheapest menu and return the quantity of each
// ingredient in it, in the same order as "price_per_ingredient".
// For example, if the cheapest menu is:
// 0.3kg of potatoes patates, 0kg of rice, 0.2kg of orange juice, ...
// Then the returned array would be: [0.3, 0, 0.2, ...].
vector<double> MenuMoinsCher(const vector<double>& dra,
const vector<vector<double>>& nutri_values_per_ingredient,
const vector<double>& price_per_ingredient);
#endif // __MENU_H
Test: make menu
#ifndef __FLOW_H
#define __FLOW_H
#include <vector>
using std::vector;
// The problem is the assignment of network traffic in a backbone network,
// which is a weighted directed graph (each arc's weight is its bandwidth
// capacity, in Gb/s).
// The graph is given as its number of nodes N and the list of its
// weighted arcs (from, to, capacity), where "from" and "to" are nodes
// (i.e. integers between 0 and N-1, inclusive), and "capacity" is the
// bandwidth in Gb/s.
// A set of network traffic business demands is also given, as a list of
// (source, destination, max bandwidth, price per Gb/s): each such demand
// corresponds to what a client is willing to pay to send some traffic from
// the node "source" to the node "destination", using our network. If we
// do provide some bandwidth on our links to satisfy that demand (even
// partially), the client will pay us the given price per Gb/s we give them,
// up to the max bandwidth limit.
//
// Which business demands, and how much of which, should we fulfill?
// How shall we route the corresponding traffic?
struct BackboneArc {
int from; // A node
int to; // A node
double capacity; // >= 0
};
struct FlowDemand {
int src; // Source: a node
int dst; // Destination: a node
double demand; // >= 0
double price; // per unit of demand (max profit = demand * price)
};
struct FlowOnArc {
int arc_index; // Index in the "backbone" input argument.
int demand_index; // Index in the "demands" input argument.
double flow;
};
vector<FlowOnArc> BestFlow(int num_nodes,
const vector<BackboneArc>& backbone,
const vector<FlowDemand>& demands);
#endif // __FLOW_H
Test: make flow