Suppose you are in charge of an advertising platform that allows a client $($advertiser$)$ to bid on dif$-$ ferent keywords, say, in the context of a search engine $($e$.$g$.,$fast solutions$,$algorithm$,$machine learning solution$,$ etc$).$ For every possible keyword, such as $$algorithm$,$ the client may specify a certain budget balgorithm, which translates into a certain number of impressions, and eventually a certain amount of new traffic towards client$$s website. Your client obviously wants to increase the total amount of new traffic to their website, by way of allocating their total ad budget to various relevant keywords.

In order to improve the experience, you decide to offer to the clients a service that, given their total ad budget B$,$ will automatically allocate the budget among the keywords maximizing the total $($projected$)$ traffic to client$$s website. To model the latter, you already have a $$prediction$$ algorithm f which maps a pair of $($keyword k$,$ dollar amount d$)$ into traffic amount. $($Note that the function is specific to each client, but this is not relevant here as we consider one client only at a time.$)$

We formalize the problem as follows. Let n be the number of different keywords. You have access to the function f $($k$,$ d$)>=0$ denoting the ad traffic generated by spending d dollars on keyword k$.$ Then given the total budget B $>0$ of dollars to spend on the ads, you need to find the best way to allocate the budget amongst n keyword to maximize the total ad traffic. In particular determine integers b$1,...$bn $>=0$ with Pnk$=1$ bk $=$ B that maximizes Pnk$=1$ f$($k$,$bk$).$

We will consider various solutions depending on properties of the function f$.$ As you will see, the properties of the function f can affect dramatically what algorithms we deploy.

Problem$1.$ Supposethefunctionf$($k$,$d$)$islinear:f$($k$,$d$)=$ak$$dwhereak$>0$aresomefixed constants $($denoting traffic per dollar for the fixed keyword k$).$ Design an algorithm that allocates the budget maximizing the ad traffic. $($Hint: note that in that case you can assign the entire budget

$1$

to a single keyword.$)$ Your algorithm should run in time O$($n$)$ only.

The above assumption of linearity of the function f is generally too simplistic: for example, some keywords are rare and hence the ad traffic may $$saturate$.$ Now suppose the function f is arbitrary, with the natural property that it is non$-$decreasing in the dollar amount d: namely, f $($k$,$ d $+1)>=$ f $($k$,$ d$)$ for all k in $[$n$],$ d $>=0.$

For this version, you can design a dynamic programming solution as follows. Define T$($k$,$b$)$ as being the maximum ad traffic that can be generated from the best allocation of the budget b to the the keywords $\{1,...$k$\}$ only. Note that T$($n$,$B$)$ is the overall maximum ad budget achievable $($i$.$e$.,$ the answer to the full problem$).$

Problem $2.$ Develop the recurrence for the quantity T$($k$,$b$)$: i$.$e$.,$ show how to compute T$($k$,$b$)$ from T $($i$,$ j$)$ where i $<=$ k and b $<=$ j $($with one of them being a strict inequality$).$

Problem $3.$ What is the resulting runtime of the algorithm?

It may be possible to make the solution more efficient if we assume some extra properties of the function f$.$ A particularly natural property is that of law of diminishing returns, which means that adding more dollars to the same keyword will result in smaller increases in traffic: i$.$e$.,$ f $($i$,$ d $+1)$ f $($i$,$ d$)<=$ f $($i$,$ d$)$ f $($i$,$ d $1)$ for any d $>=1.$

Problem $4.$ Suppose the optimal allocation of B dollars is to allocate di dollars for keyword i$,$ where B $=$ Pi di$.$ Now suppose we have one extra dollar to spend. What is the best allocation now, i$.$e$.,$ for a budget of B $+1?($Hint: it would be a simple modification$/$extension of allocation d$1,$d$2,...$dn$.)$

Problem $5.$ Now design a greedy algorithm for this problem $($under the law of diminishing returns property$)$ with a runtime of O$($nB$).$please share all python codes.