1) Implement the Counting Sort algorithm using your favorite programming languag
ID: 3699581 • Letter: 1
Question
1) Implement the Counting Sort algorithm using your favorite programming language. a) Upon running, your program should prompt the user for the input array size b) Then your program should generate an array of requested size and fill it with random integers between 1 and 100 (so in Counting sort your k-100, which means the 'C' array should have indices from 0 to 100) c) Print the generated random array d) Finally, print the sorted array. 2) Implement the Fractional Knapsack problem using your favorite programming language. pt the user for item weights. b) Then prompt the user for item values. c) Then prompt the user for the knapsack weight rating (W) d) Print each and every greedy choice. That is the items that are selected and how much of each.Explanation / Answer
Solution for Q1 >>>>>>>>>>>
#include <iostream>
using namespace std;
#define MAX 101
#define MIN 0
int main()
{
int arr[MAX];
int n,i,j;
int temp;
//read array size
cout<<"Enter Array Size: ";
cin>>n;
//check for valid array size
if(n<0 || n>MAX)
{
cout<<"Invalid range !"<<endl;
return -1;
}
//Generate randon number between 0 to 100 and fill it in array
for(i=0;i<n;i++)
{
arr[i] = rand()%(100-MIN + 1) + MIN;
}
//print input elements
cout<<"Generated Random Array :"<<endl;
for(i=0;i<n;i++)
cout<< "arr["<<i<<"] "<< arr[i]<<endl;
cout<<endl;
//sorting of arrray elements
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[i]>arr[j])
{
temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
//print sorted array
cout<<"Sorted Array elements:"<<endl;
for(i=0;i<n;i++)
cout<< "arr["<<i<<"] "<<arr[i]<<endl;
cout<<endl;
return 0;
}
<<<<<<<<< Output >>>>>>>>>
Enter Array Size: 101
Generated Random Array :
arr[0] 32
arr[1] 32
arr[2] 54
arr[3] 12
arr[4] 52
arr[5] 56
arr[6] 8
arr[7] 30
arr[8] 44
arr[9] 94
arr[10] 44
arr[11] 39
arr[12] 65
arr[13] 19
arr[14] 51
arr[15] 91
arr[16] 1
arr[17] 5
arr[18] 89
arr[19] 34
arr[20] 25
arr[21] 58
arr[22] 20
arr[23] 51
arr[24] 38
arr[25] 65
arr[26] 30
arr[27] 7
arr[28] 20
arr[29] 10
arr[30] 51
arr[31] 18
arr[32] 43
arr[33] 71
arr[34] 97
arr[35] 61
arr[36] 26
arr[37] 5
arr[38] 57
arr[39] 70
arr[40] 65
arr[41] 0
arr[42] 75
arr[43] 29
arr[44] 86
arr[45] 93
arr[46] 87
arr[47] 87
arr[48] 64
arr[49] 75
arr[50] 88
arr[51] 89
arr[52] 100
arr[53] 7
arr[54] 40
arr[55] 37
arr[56] 38
arr[57] 36
arr[58] 44
arr[59] 24
arr[60] 46
arr[61] 95
arr[62] 43
arr[63] 89
arr[64] 32
arr[65] 5
arr[66] 15
arr[67] 58
arr[68] 77
arr[69] 72
arr[70] 95
arr[71] 8
arr[72] 38
arr[73] 69
arr[74] 37
arr[75] 24
arr[76] 27
arr[77] 90
arr[78] 77
arr[79] 92
arr[80] 31
arr[81] 30
arr[82] 80
arr[83] 30
arr[84] 37
arr[85] 86
arr[86] 33
arr[87] 76
arr[88] 21
arr[89] 77
arr[90] 100
arr[91] 68
arr[92] 37
arr[93] 8
arr[94] 22
arr[95] 69
arr[96] 81
arr[97] 38
arr[98] 94
arr[99] 57
arr[100] 76
Sorted Array elements:
arr[0] 0
arr[1] 1
arr[2] 5
arr[3] 5
arr[4] 5
arr[5] 7
arr[6] 7
arr[7] 8
arr[8] 8
arr[9] 8
arr[10] 10
arr[11] 12
arr[12] 15
arr[13] 18
arr[14] 19
arr[15] 20
arr[16] 20
arr[17] 21
arr[18] 22
arr[19] 24
arr[20] 24
arr[21] 25
arr[22] 26
arr[23] 27
arr[24] 29
arr[25] 30
arr[26] 30
arr[27] 30
arr[28] 30
arr[29] 31
arr[30] 32
arr[31] 32
arr[32] 32
arr[33] 33
arr[34] 34
arr[35] 36
arr[36] 37
arr[37] 37
arr[38] 37
arr[39] 37
arr[40] 38
arr[41] 38
arr[42] 38
arr[43] 38
arr[44] 39
arr[45] 40
arr[46] 43
arr[47] 43
arr[48] 44
arr[49] 44
arr[50] 44
arr[51] 46
arr[52] 51
arr[53] 51
arr[54] 51
arr[55] 52
arr[56] 54
arr[57] 56
arr[58] 57
arr[59] 57
arr[60] 58
arr[61] 58
arr[62] 61
arr[63] 64
arr[64] 65
arr[65] 65
arr[66] 65
arr[67] 68
arr[68] 69
arr[69] 69
arr[70] 70
arr[71] 71
arr[72] 72
arr[73] 75
arr[74] 75
arr[75] 76
arr[76] 76
arr[77] 77
arr[78] 77
arr[79] 77
arr[80] 80
arr[81] 81
arr[82] 86
arr[83] 86
arr[84] 87
arr[85] 87
arr[86] 88
arr[87] 89
arr[88] 89
arr[89] 89
arr[90] 90
arr[91] 91
arr[92] 92
arr[93] 93
arr[94] 94
arr[95] 94
arr[96] 95
arr[97] 95
arr[98] 97
arr[99] 100
arr[100] 100
Solution For Q2 >>>>>>>>
#include<stdio.h>
#include<iostream>
using namespace std;
void printChoice(int weights[], int values[], int n)
{
int i, j;
cout << " Items to be selected :";
i = 0;
cout<< i;
for (j = 1; j < n; j++)
{
if (weights[j] >= values[i])
{
cout << " " << j;
i = j;
}
}
}
int main()
{
int i;
int weights[6];
int values[6];
cout<<"Enter Weights : ";
for(i=0;i<6;i++)
{
cin>>weights[i];
}
cout<<"Enter Values : ";
for(i=0;i<6;i++)
{
cin>>values[i];
}
cout<<"weights are : ";
for(i=0;i<6;i++)
{
cout<<weights[i]<<" ";
}
cout<<endl;
cout<<"values are : ";
for(i=0;i<6;i++)
{
cout<<values[i]<<" ";
}
cout<<endl<<endl;
int n = sizeof(weights)/sizeof(weights[0]);
printChoice(weights, values, n);
return 0;
}
<<<<<<<<<<< Output >>>>>>>>>>
Enter Weights : 1
3
0
5
8
5
Enter Values : 2
4
6
7
9
9
weights are : 1 3 0 5 8 5
values are : 2 4 6 7 9 9
Items to be selected :0 1 3 4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.