Solving the most profit algorithm [closed]

2024/12/9 21:11:39

I am practicing algorithms for upcoming job interviews and I am having trouble correctly implementing this one. I am trying to also maximize efficiency as well. Here is the problem:

Maximize the profit of your business selling metal rods. If you sell N metal rods of length L, you receive N * L * metal_price. The remaining smaller metal rods will be trashed. To cut metal rods, you need to pay cost_per_cut for every cut. What is the max profit you can make?

constraints:
lengths will be 1 to 50 elements, inclusive.
each element of length will lie in range [1,10000]
1 <= metal_price, cost_per_cut <=1000

sample input:

cost_per_cut =1metal_price =10lengths = [26,103, 59]return: 1770

how the book solved this is that the most optimal length of rod is 6. so we cut 4 pieces of length 6 from 1st rod, and throw piece of length 2 from it. next we cut 17 pieces of length 6 from 2nd rod, and throw away piece of length 1. for the third, we cut 9 pieces of length 6, and throw a piece of length 5. so in total we have made 30 cuts. therefore, 30*6*10 - 30*1 - 1770

Here is my attempt so far:

def  maxProfit( cost_per_cut,  metal_price,  lengths):profit =0for num in lengths:

I'm just not really sure how to go about doing this. Should I iterate over the numbers and see what the lowest number they're divisible by and use that? Any ideas?

Answer

Since the input ranges are quite small, can you not just brute force this

    static int getProfit(int[] rods, int cutCost, int metalPrice, int L){int profit = 0;foreach (int rod in rods){if (rod % L == 0){profit += (metalPrice * rod - (rod / L - 1) * cutCost);}else{profit += (metalPrice * (rod - rod % L) - (rod / L) * cutCost);}}return profit;}static void Main(string[] args){int[] rods = new int[] { 26,103,59};int cutCost =1;int metalPrice=10;int maxProfit = 0;for (int L = 1; L <= 10000; ++L){int profit= getProfit(rods, cutCost, metalPrice, L);if (profit > maxProfit){maxProfit = profit;}}Console.WriteLine(maxProfit);}
https://en.xdnf.cn/q/72888.html

Related Q&A

Get combobox value in python

Im developing an easy program and I need to get the value from a Combobox. It is easy when the Combobox is in the first created window but for example if I have two windows and the Combobox is in the s…

PyAudio (PortAudio issue) Python

I installed pyaudio with anaconda python. Using conda install pyaudio on windows. It said it installed and it also installed PortAudio with it.However, when I create my file and run it now I get the fo…

Python multiprocessing with M1 Mac

I have a mac (Mac Os 11.1, Python Ver 3.8.2) and need to work in multiprocessing, but the procedures doesn’t work. import multiprocessingdef func(index: int):print(index)manager = multiprocessing.Mana…

What is faster in Python, while or for xrange

We can do numeric iteration like:for i in xrange(10):print i,and in C-style:i = 0 while i < 10:print i,i = i + 1Yes, I know, the first one is less error-prone, more pythonic but is it fast enough as…

Concatenate Numpy arrays with least memory

Not I have 50GB dataset saved as h5py, which is a dictionary inside. The dictionary contains keys from 0 to n, and the values are numpy ndarray(3 dimension) which have the same shape. For example:dicti…

How to generate random programs from BNF

I know my question sounds a little vague, but I could not find any tutorials online. I am not asking for an answer, but for more of an explanation. An example of the BNF:<prog> ::= “int main() {…

Pandas: merge multiple dataframes and control column names?

I would like to merge nine Pandas dataframes together into a single dataframe, doing a join on two columns, controlling the column names. Is this possible?I have nine datasets. All of them have the fo…

Two different plots from same loop in matplotlib?

I would specifically like to create two different plots using one single loop. One plot should have four straight lines from x-y, and another plot should have four angled lines from x-y2. My code only …

Matplotlib text alignment

Is there a way to get the result shown in the third axes with just a single ax.text() command? Using expandtabs almost get me there, but the text never aligns properly. Using two plotting commands doe…

Pandas cannot load data, csv encoding mystery

I am trying to load a dataset into pandas and cannot get seem to get past step 1. I am new so please forgive if this is obvious, I have searched previous topics and not found an answer. The data is mos…