Question

Truck Loading Problem Description: You seek to select most profitable collection of items that you can transport on a truck. Each item has a profit and a weight associated with it, and the truck has a maximum weight limit that cannot be exceeded. Inputs:  profit[], an array of non-negative floating point numbers, where the i th entry in the array corresponds to the value of the i th item  weights[], an array of non-negative integers, where weights[i] equals the size of the i th item  limit, the maximum weight limit for the truck Return: select[], an array of values, where the i th entry in the array is 1 if i th item is included in the collection of items to be loaded, and 0 otherwise. The values in the select[] array are ones that maximize the profit, where: ?????? = ∑ ??????[?] ∙ ??????[?] ?−1 ?=0 Subject to the constraints: ∑ ??????[?] ∙ ????ℎ??[?] ≤ ????? ?−1 ?=0 ??????[?] ∈ {0,1} Consider the following heuristics (rules) used in selecting the next component in greedy algorithms. Would the resulting algorithm be correct? Justify your answers. (5 points each) 1a. Earliest item first (select the item with the smallest index in the weight and profit arrays, subject to the limit constraint). 1b. Lightest item first (select the lightest of the remaining items, subject to the limit constraint). 1c. Heaviest item first (select the heaviest of the remaining items, subject to the limit constraint). 1d. Highest value item first (select the item with the largest value of the remaining items, which would not violate the limit constraint). 1e. Lowest value item first (select the item with the smallest value of the remaining items, which would not violate the limit constraint). 1e. Highest value per pound first (select the item with the largest ratio of profit to weight, from the collection of items that would not violate the limit constraint). 1f. Highest weight per value first (select the item with the largest ratio of weight to profit, from the collection of items that would not violate the limit constraint).

Truck Loading Problem for Sand Delivery Company Description: You seek to select most profitable collection of sand that you can transport on a truck. As before, each type of sand has a profit and a weight associated with it, and the truck has a maximum weight limit that cannot be exceeded. However, you can choose to load just a portion of a type of sand on the truck. Inputs:  profit[], an array of non-negative floating point numbers, where the i th entry in the array corresponds to the value of the i th type of sand  weights[], an array of non-negative integers, where weights[i] equals the total amount of the i th type of sand  limit, the maximum weight limit for the truck Return: select[], an array of values, where the i th entry in the array represents the fraction of the i th type of sand that is to be loaded, and 0 if no sand of the i th type of sand is taken. The values in the take[] array are ones that maximize the profit, given by the following expression: ?????? = ∑ ??????[?] ∙ ??????[?] ?−1 ?=0 Subject to the constraints: ∑ ??????[?] ∙ ????ℎ??[?] ≤ ????? ?−1 ?=0 0 ≤ ??????[?] ≤ 1 2a. Write an algorithm (using pseudocode) that provides an efficient solution to this problem. The pseudocode should contain enough detail so that it is possible to analyze the running time and correctness of the algorithm. Note that an efficient algorithm will run in time that is bounded above by a polynomial. (30 points) 2b. Express the worst case time complexity of your algorithm using asymptotic notation. Justify your answer. (5 points) 2c. Prove that your algorithm is correct. (30 points)

Answer 1

1a. Earliest item first (select the item with the smallest index in the weight and profit arrays, subject to the limit constraint).

--> No, As the earliest item in the array may not be the best one to select for eg

itemWeight = [10,2,3,4,5]

valuePerUnit = [1,20,30,40,50]

Clearly, by choosing 10 units of item 1 (assuming that it is still in limit) is no good as profit earned is only 10 (10 units * profit per unit which is 1)

1b. Lightest item first (select the lightest of the remaining items, subject to the limit constraint).

--> Not necessarily true as per the eg below, the lightest article is at index 0 which has a profit of only 1 per unit weight.

itemWeight = [1,2,3,4,5]

valuePerUnit = [1,20,30,40,50]

1c. Heaviest item first (select the heaviest of the remaining items, subject to the limit constraint).

Not necessarily true, similar to explanation in 1b

1d. Highest value item first (select the item with the largest value of the remaining items, which would not violate the limit constraint).

--> Not necessarily true as there might be a more optimum solution available.

1e. Lowest value item first (select the item with the smallest value of the remaining items, which would not violate the limit constraint). 1e. Highest value per pound first (select the item with the largest ratio of profit to weight, from the collection of items that would not violate the limit constraint).

--> Clearly not best solution as the goal is to maximize the profit.

1f. Highest weight per value first (select the item with the largest ratio of weight to profit, from the collection of items that would not violate the limit constraint).

--> Clearly the best approach since we select the items which give is maximum profit per unit.

Algorithm:

1) Compute the profitPerUnitWeight for each item and store it in profitPerUnitWeight[], mark each item as unselected i.e

selected[] = 0 for all items

2) Let W denote the total weight that can be put on the truck, do step 3

3) Select the unselected item (item which still has selected[]=0) with highest profitPerUnitWeight

4) If the weight of selected item is less than W, mark the item selected[] = 1 and set W = W - weight of selected item

5) if W>0 and there is atleast 1 unselected item, goto step 3

Clearly, we traverse each entry of a 2D array of size N*W where N is the total number of items and W is the total weight, the run time complexity hence becomes O(nw)