answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Elena L [17]
2 years ago
5

You are consulting for a trucking company that does a large amount ofbusiness shipping packages between New York and Boston. The

volume ishigh enough that they have to send a number of trucks each day betweenthe two locations. Trucks have a fixed limit w on the maximum amountof weight they are allowed to carry. Boxes arrive at the New York stationone by one, and each package i has a weight wi. The trucking stationis quite small, so at most one truck can be at the station at any time.Company policy requires that boxes are shipped in the order they arrive;otherwise, a customer might get upset upon seeing a box that arrivedafter his make it to Boston faster. At the moment, the company is usinga simple greedy algorithm for packing: they pack boxes in the order theyarrive, and whenever the next box does not fit, they, send the truck on itsway.But they wonder if they might be using too many trucks, and theywant your opinion on whether the situation can be improved. Here ishow they are thinking. Maybe one could decrease the number of trucksneeded by sometimes sending off a truck that was less full, and in thisway allow the next few trucks to be better packed.Prove that, for a given set of boxes with specified weights, the greedyalgorithm currently in use actually minimizes the number of trucks thatare needed. Your proof should follow the type of analysis we used forthe Interval Scheduling Problem: it should establish the optimality of thisgreedy packing algorithm by identifying a measure under which it "staysahead" of all other solutions.
Computers and Technology
1 answer:
likoan [24]2 years ago
6 0

Answer:

Answer explained with detail below

Explanation:

Consider the solution given by the greedy algorithm as a sequence of packages, here represented by indexes: 1, 2, 3, ... n. Each package i has a weight, w_i, and an assigned truck t_i. { t_i } is a non-decreasing sequence (as the k'th truck is sent out before anything is placed on the k+1'th truck). If t_n = m, that means our solution takes m trucks to send out the n packages.

If the greedy solution is non-optimal, then there exists another solution { t'_i }, with the same constraints, s.t. t'_n = m' < t_n = m.

Consider the optimal solution that matches the greedy solution as long as possible, so \for all i < k, t_i = t'_i, and t_k != t'_k.

t_k != t'_k => Either

1) t_k = 1 + t'_k

    i.e. the greedy solution switched trucks before the optimal solution.

    But the greedy solution only switches trucks when the current truck is full. Since t_i = t'_i i < k, the contents of the current truck after adding the k - 1'th package are identical for the greedy and the optimal solutions.

    So, if the greedy solution switched trucks, that means that the truck couldn't fit the k'th package, so the optimal solution must switch trucks as well.

    So this situation cannot arise.

  2) t'_k = 1 + t_k

     i.e. the optimal solution switches trucks before the greedy solution.

     Construct the sequence { t"_i } s.t.

       t"_i = t_i, i <= k

       t"_k = t'_i, i > k

     This is the same as the optimal solution, except package k has been moved from truck t'_k to truck (t'_k - 1). Truck t'_k cannot be overpacked, since it has one less packages than it did in the optimal solution, and truck (t'_k - 1)

     cannot be overpacked, since it has no more packages than it did in the greedy solution.

     So { t"_i } must be a valid solution. If k = n, then we may have decreased the number of trucks required, which is a contradiction of the optimality of { t'_i }. Otherwise, we did not increase the number of trucks, so we created an optimal solution that matches { t_i } longer than { t'_i } does, which is a contradiction of the definition of { t'_i }.

   So the greedy solution must be optimal.

You might be interested in
In the context of the components of a typical expert system, _____ is a software package with manual or automated methods for ac
Pani-rosa [81]

Answer:

knowledge acquisition facility

Explanation:

In the context of the components of a typical expert system, Knowledge acquisition facility is defined as that component of an expert system that is responsible for providing an effective and efficient medium for collecting and incorporating relevant information such as data, new rules, relationships and facts used by the expert system.

6 0
2 years ago
Write a program named as calcPrice.c that formats product information entered by the user and calculate the total amount of purc
Colt1911 [192]

Answer:

Here is the calcPrice.c program:

#include <stdio.h>   //to use input output functions

int main(void)  {  //start of main method

   int itemNo, month, day, year, quantity;  //declares variables to hold item number, quantity, and date

   float unitPrice; //declare variable to hold price per unit

   printf("Enter item number: ");  // prompts user to enter item number

   scanf("%d", &itemNo);  //reads item number from user and stores it in itemNo variable

   printf("Enter unit price: ");  // prompts user to enter unit price

   scanf("%f", &unitPrice);  //reads input unit price and stores it in unitPrice variable

   

    printf("Enter quantity: ");  //prompts user to enter quantity

   scanf("%d", &quantity);  //reads input quantity and stores it in quantity variable

   printf("Enter purchase date (mm/dd/yyyy): ");  //prompts user to enter purchase date

   scanf("%d/%d/%d", &month, &day, &year);  //reads input date and stores it in month, day and year variables

    float totalAmount = unitPrice * quantity;  //computes the total amount

   printf("\nItem\tUnit Price\tQTY\tPurchase Date\tTotal Amount\n");  //displays the item, unit price, qty, purchase data and total amount with tab space between each

   printf("%d\t$%5.2f\t%d\t%.2d/%.2d/%d\t$%5.2f\n", itemNo, unitPrice,quantity, month, day, year,totalAmount);   }    //displays the values of itemNo, unitPrice, quantity, month, day, year and computed totalAmount with tab space between each

Explanation:

Lets suppose user enters 583 as item number, 13.5 as unit price, 2 as quantity and 09/15/2016 as date so

itemNo = 583

unitPrice = 13.5

quantity = 2

month = 09

day = 15

year = 2016

totalAmount is computed as:

  totalAmount = unitPrice * quantity;

 totalAmount = 13.5* 2

totalAmount = 27.00

Hence the output of the entire program is:

Item    Unit Price      QTY     Purchase Date   Total Amount      

583     $  13.50           2           09/15/2016         $  27.00  

The screenshot of the program along with its output is attached.

4 0
2 years ago
HELP ME ON THIS PLEASE ILL GIVE BRAINLY!!!! If U GET IT RIGHT !!!
kherson [118]

Answer:

Opportunity cost doesn't only occur when you spend money. For example, if I can eat one snack at a party and I like both cake and cookies, I have to choose one over the other. This is an example of opportunity cost without spending money.

3 0
1 year ago
Acceleration is the rate at which an object changes its velocity. It is typically represented by symbol a and measured in m/s2 (
Natalija [7]

Answer:

<u>Pseudocode:</u>

INPUT velocity

INPUT time

SET velocity = 0.44704 * velocity

SET acceleration = velocity / time

SET acceleration = round(acceleration, 1)

PRINT acceleration

<u>Code:</u>

velocity = float(input("Enter a velocity in miles per hour: "))

time = float(input("Enter a time in seconds: "))

velocity = 0.44704 * velocity

acceleration = velocity / time

acceleration = round(acceleration, 1)

print("The acceleration is {:.2f}".format(acceleration))

Explanation:

*The code is in Python.

Ask the user to enter the velocity and time

Convert the miles per hour to meters per second

Calculate the acceleration using the formula

Round the acceleration to one decimal using round() method

Print the acceleration with two decimal digits

7 0
2 years ago
Which type of wireless technology bounces transmissions off walls and ceilings to deliver signals from sender to receiver and is
Alenkinab [10]
Scatter infrared. Hope this helps! <span />
7 0
2 years ago
Other questions:
  • Match the careers with the career clusters.
    5·2 answers
  • Fill in the blank; "As well as their traditional role of computing data, computers are also extensively used for..."
    14·1 answer
  • Give a recursive (or non-recursive) algorithm to compute the product of two positive integers, m and n, using only addition and
    8·1 answer
  • Suppose Dave drops a watermelon off a high bridge and lets it fall until it hits the water. If we neglect air resistance, then t
    12·1 answer
  • Sean is forecasting the time and cost of developing a customized software program by looking at the number of inputs, outputs, i
    8·1 answer
  • Use the following data definitions data myBytes BYTE 10h,20h,30h,40h myWords WORD 3 DUP(?),2000h myString BYTE "ABCDE" What will
    9·1 answer
  • Server farms such as Google and Yahoo! provide enough compute capacity for the highest request rate of the day. Imagine that mos
    12·1 answer
  • Temperature Class Write a Temperature class that will hold a temperature in Fahrenheit and provide methods to get the temperatur
    6·1 answer
  • Do Exercise 6.4 from your textbook using recursion and the is_divisible function from Section 6.4. Your program may assume that
    6·1 answer
  • Stan’s assignment is to print a three-dimensional image on a piece of paper. Which printing technique should he use?
    14·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!