Design and Analysis of Algorithms - 8

by

Implement Program for fractional knapsack using Greedy design technique.


Code:


#include <stdio.h>

 

void main()

{

    int capacity, no_items, cur_weight, item;

    int used[10];

    float total_profit;

    int i;

    int weight[10];

    int value[10];

 

    printf("Enter the capacity of knapsack:\n");

    scanf("%d", &capacity);

 

    printf("Enter the number of items:\n");

    scanf("%d", &no_items);

 

    printf("Enter the weight and value of %d item:\n", no_items);

    for (i = 0; i < no_items; i++)

    {

        printf("Weight[%d]:", i);

        scanf("%d", &weight[i]);

        printf("Value[%d]:", i);

        scanf("%d", &value[i]);

    }

 

    for (i = 0; i < no_items; ++i)

        used[i] = 0;

 

    cur_weight = capacity;

    while (cur_weight > 0)

    {

        item = -1;

        for (i = 0; i < no_items; ++i)

            if ((used[i] == 0) &&

                ((item == -1) || ((float) value[i] / weight[i] > (float) value[item] / weight[item])))

                item = i;

 

        used[item] = 1;

        cur_weight -= weight[item];

        total_profit += value[item];

        if (cur_weight >= 0)

            printf("\nAdded object %d (%d Rs., %dKg) completely in the bag. Space left: %d.\n", item + 1, value[item], weight[item], cur_weight);

        else

        {

            int item_percent = (int) ((1 + (float) cur_weight / weight[item]) * 100);

            printf("Added %d%% (%d Rs., %dKg) of object %d in the bag.\n", item_percent, value[item], weight[item], item + 1);

            total_profit -= value[item];

            total_profit += (1 + (float)cur_weight / weight[item]) * value[item];

        }

    }

 

    printf("\nFilled the bag with objects worth %.2f Rs.\n", total_profit);

}


Output:

 


 

 

 









Conclusion:


In this Practical, I understand to Implement program of Counting Sort.

Here counting sort is effective when range is not greater than number of objects to be sorted.

Counting sort used to sort the negative input values.

 

 


Comments

Post a Comment

Popular posts from this blog

Computer Architecture and Organization - 4

by
Image
Aim:  To implement various 4-bit arithmetic Micro-operations           using arithmetic unit.   Theory Arithmetic micro operation of the form L:   R A  ( R A + R B ) refers to two data items contained in R A and R B input to a parallel adder with the result being stored back in R A (Fig.). Loading      of the result in R A is subject to the availability   of the control   signal designated as L   (that   is   load control of R A ) . Note that adder being a combinational logic, the adder output is available after a delay of the associated combinational circuit. Input to adder may be also controlled by providing AND word gates on the data paths from R A and R B to the adder under the control signal C (Fig.). the control signals `C' and 2's complement are at logic `0' for add operation.   The subtract micro operation L:   R A  ( R A - R B ) in 2's comp...
Read more

Design and Analysis of Algorithms - 2

by
Image
Implement functions to print n th Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. Code:   #include<stdio.h>   int count_ite=0; int count_rec=0; void febo_ite(int ); int febo_rec(int );   int main() {     int n,ans;     printf("Enter position of number: ");     scanf("%d",&n);     febo_ite(n);     ans=febo_rec(n);     printf("Using Recursion: %d th number is = %d\n",n,ans);     printf("No of Steps= %d\n\n",count_rec); }   void febo_ite(int n) {     count_ite++;     int next,i, first=0,second=1;     count_ite++;     if(n==0)     {         count_ite++;  ...
Read more

Design and Analysis of Algorithms - 6

by
Image
Implement program for randomized version of quick sort and compare its performance with normal version of quick sort using steps count on various number of inputs.   Code: #include<stdio.h> #include<stdlib.h> #include<time.h>   int count=0; int r_count=0; void quick_sort(int a[],int start,int n) {     int i,j,pivot,temp;     count++;     if(start<n)         {             count++;             pivot=start;             count++;             i=start;             count++;             j=n;     ...
Read more

Design and Analysis of Algorithms - 1

by
Image
Implement a function for each of following problems and count the  number of steps executed/Time taken by each function on various  inputs and write complexity of each function. Also draw a  comparative chart. In each of the following function N will be passed  by user.                     1. To calculate sum of 1 to N number using loop.                     2. To calculate sum of 1 to N number using equation.                     3. To calculate sum of 1 to N numbers using recursion. Code:   #include <stdio.h> int count_loop=0; int count_rec=0; int count_eq=0;   int sum_loop(int n) {     int i,sum=0;     count_loop++;     for(i=1;i<=n;i++)     {         count_loop++; ...
Read more

Artificial Intelligence - 7

by
Image
  AIM: Write a program to build Multi-layer Perceptron to implement any Boolean functions as mentioned below without using any python packages. AND, OR, XOR, XNOR, NOR, NAND, NOT x1, NOT x2, NULL, IDENTITY, INHIBITION ( 𝑥 1 ∧ ¬ 𝑥 2), INHIBITION ( 𝑥 2 ∧ ¬ 𝑥 1), TRANSFER x1, TRANSFER x2, IMPLICATION ( 𝑥 1 ∨ ¬ 𝑥 2), IMPLICATION ( 𝑥 2 ∨ ¬ 𝑥 1)   Program: class  perceptronNeuron:      def   __init__ ( self ,  x ,  w ,  w0 ):         l = [ww  for  ww  in  x]         l.insert( 0 ,  1 )          self .x = l          self .y =  0         l = [ww  for  ww  in  w]         l.insert( 0 ,...
Read more