Data Structures and Problem Solving Using Java 4th edition exercise 21.25 Suppos
ID: 3719487 • Letter: D
Question
Data Structures and Problem Solving Using Java 4th edition
exercise 21.25
Suppose that you have a number of boxes, each of which can hold total weight 1.0 and items i1, i2, i3, ..., iN, which weigh w1, w2, w3, ..., wN, respectively. The object is to pack all the items, using as few boxes as possible, without placing more weight in any box than its capacity. For instance, if the items have weights 0.4, 0.4, 0.6, and 0.6, you can solve the problem with two boxes. This problem is dif?cult, and no ef?cient algorithm is known. Several strategies give good, but not optimal, packings. Write programs to implement ef?ciently the following approximation strategies. a. Scan the items in the order given; place each new item in the most-?lled box that can accept it without over?owing. Use a priority queue to determine the box that an item goes in. b. Sort the items, placing the heaviest item ?rst; then use the strategy in part (a).
Explanation / Answer
package javaapplication35;
import java.util.Scanner;
class Weight{
int N,usedboxes;
double item_weight[];
double number_weight[];
public Weight()
{
Scanner input= new Scanner(System.in);
int i;
System.out.print(" Eneter the Number of Item:");
N=input.nextInt();
item_weight=new double[N];
number_weight=new double[N];
System.out.print(" Eneter the WWeght of "+ N+ " Item:");
for(i=0;i<N;i++)
item_weight[i]=input.nextDouble();
usedboxes=0;
input.close();
}
public void assignWeight()
{
int i,j;
number_weight[usedboxes++]=item_weight[0];
for(i=1;i<N;i++)
{
j=0;
while(((number_weight[j]+item_weight[i])>1)&&(j<usedboxes))
{
j++;
}
if(j==usedboxes)
number_weight[usedboxes++]=item_weight[i];
else
{
number_weight[usedboxes]=item_weight[i];
}
}
}
void display()
{
int i;
System.out.print(" Boxes are used and contain weight: ");
for(i=0;i<usedboxes;i++)
System.out.print(number_weight[i]+" ");
}
public void sort()
{
int i,j,max;
double t;
for(i=0;i<N-1;i++)
{
max=i;
for(j=i+1;j<N;j++)
if(item_weight[j]>item_weight[max])
max=j;
if(max!=i)
{
t= item_weight[max];
item_weight[max]=item_weight[i];
item_weight[i]=t;
}
}
}
public void assignWeightsort()
{
int i,j;
usedboxes=0;
number_weight[usedboxes++]=item_weight[0];
for(i=1;i<N;i++)
{
j=0;
while(((number_weight[j]+item_weight[i])>1)&&(j<usedboxes))
{
j++;
}
if(j==usedboxes)
number_weight[usedboxes++]=item_weight[i];
else
{
number_weight[usedboxes]+=item_weight[i];
}
}
}
}
public class WeightAssignment {
public static void main(String[] args) {
Weight w=new Weight();
System.out.print(" Assignmeent before Sorting ");
w.assignWeight();
w.display();
System.out.print(" Assignmeent Afetr Sorting ");
w.sort();
w.assignWeightsort();
w.display();
}
}
run:
Eneter the Number of Item:5
Eneter the WWeght of 5 Item:.7
.8
.9
.2
.1
Assignmeent before Sorting
Boxes are used and contain weight:
0.7 0.8 0.9
Assignmeent Afetr Sorting
Boxes are used and contain weight:
0.9 0.8 0.7 BUILD SUCCESSFUL (total time: 31 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.