4.Fractional Knapsack

PHOTO

Sun Nov 03 2024 12:45:43 GMT+0000 (Coordinated Universal Time)

Task-4
Implement Fractional Knapsack Algorithm
Algorithm:
Algorithm Sort(p, w, n){
  int r[n], index[n];
  int p[n], w[n];
  
  for i := 1 to n
    r[i] := p[i] / w[i];
  
  for i := n to n do{
    j := i;
    for k := i + 1 to n do
      if (r[k] <= r[j]) then 
	j := k;
    if(j!-i){
     index[i] := j;
     t := r[i];
     r[i] := r[j];
     r[j] := t;
    }
  }
  
  for i := 1 to n
  {
    p[i] := p[index[i]];
    w[i] := w[index[i]];
  }
}
Program:
#include <stdio.h>

void knapsack(int n, float weight[], float profit[], float capacity) {
    float tp = 0;
    int i, u;
    u = capacity;
    for (i = 0; i < n; i++) {
        if (weight[i] > u)
            break;
        else {
            tp = tp + profit[i];
            u = u - weight[i];
        }
    }
    if (i < n)
        tp = tp + (u / weight[i] * profit[i]);
    printf("\nMaximum profit is:- %f", tp);
}

int main() {
    float weight[20], profit[20], capacity;
    int num, i, j;
    float ratio[20], temp;

    printf("\nEnter the no. of objects:- ");
    scanf("%d", &num);

    printf("\nEnter the wts and profits of each object:-\n");
    for (i = 0; i < num; i++) {
        scanf("%f %f", &weight[i], &profit[i]);
    }

    printf("\nEnter the capacity of knapsack:- ");
    scanf("%f", &capacity);

    // Calculate profit/weight ratio
    for (i = 0; i < num; i++) {
        ratio[i] = profit[i] / weight[i];
    }

    // Sort items by profit/weight ratio in descending order
    for (i = 0; i < num; i++) {
        for (j = i + 1; j < num; j++) {
            if (ratio[i] < ratio[j]) {
                // Swap ratios
                temp = ratio[j];
                ratio[j] = ratio[i];
                ratio[i] = temp;

                // Swap weights and profits to keep arrays aligned
                temp = weight[j];
                weight[j] = weight[i];
                weight[i] = temp;

                temp = profit[j];
                profit[j] = profit[i];
                profit[i] = temp;
            }
        }
    }

    knapsack(num, weight, profit, capacity);
    return 0;
}
Output:
Enter the no. of objects:- 5
Enter the wts and profits of each object:-
4 12
1 2
2 2
1 1
4 10
Enter the capacity of knapsack:- 15
Maximum profit is:- 17.333334

=== Code Execution Successful ===

COPY

Save snippets that work from anywhere online with our extensions

Comments

ADA-LAB

@varuntej

1.MERGE AND QUICK SORT 2. ARTICULATION POINTS 4.Fractional Knapsack 5.Shortest Path 6.OBST 3.JOB SEQUENCING 7.Prim's Algorithm 8. Kruskal's Algorithm

c - Where is PATH_MAX defined in Linux? - Stack Overflow

#include <linux/limits.h>

char current_path[PATH_MAX];

Old Traffic System

#include "SevSeg.h"
SevSeg sevseg;

int LEDRa = 33;
int LEDGa = 32;

int LEDRb = 23;
int LEDGb = 22;

int LEDRc = 50;
int LEDGc = 51;

int LEDRd = 42;
int LEDGd = 43;

int IRa1 = 44;
int IRa2 = 52;

int IRb1 = 49;
int IRb2 = 48;

int IRc1 = 35;
int IRc2 = 37;

int IRd1 = 47;
int IRd2 = 46;

int RoadATraffic[] = {0, 0};
int RoadBTraffic[] = {0, 0};
int RoadCTraffic[] = {0, 0};
int RoadDTraffic[] = {0, 0};

char jam[] = {'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'};

void setup() {
  pinMode (LEDRa, OUTPUT);
  pinMode (LEDGa, OUTPUT);

  pinMode (LEDRb, OUTPUT);
  pinMode (LEDGb, OUTPUT);

  pinMode (LEDRc, OUTPUT);
  pinMode (LEDGc, OUTPUT);

  pinMode (LEDRd, OUTPUT);
  pinMode (LEDGd, OUTPUT);

  pinMode (IRa1, INPUT);
  pinMode (IRa2, INPUT);

  pinMode (IRb1, INPUT);
  pinMode (IRb2, INPUT);

  pinMode (IRc1, INPUT);
  pinMode (IRc2, INPUT);

  pinMode (IRd1, INPUT);
  pinMode (IRd2, INPUT);

  byte numDigits = 2;
  byte digitPins[] = {11, 10};
  byte segmentPins[] = {9, 8, 6, 3, 4, 7, 2, 5};
  bool resistorsOnSegments = true;

  byte hardwareConfig = COMMON_CATHODE;
  sevseg.begin(hardwareConfig, numDigits, digitPins, segmentPins, resistorsOnSegments);
  sevseg.setBrightness(90);

  Serial.begin(9600); // open the serial port at 9600 bps:
}

static int counter = 5;
int jam_ind = 0;
int current_route = 0;

void loop() {
    //display();
    RoadATraffic[0] = (digitalRead (IRa1) != 1) ? ( 1 ) : ( 0 );
    RoadATraffic[1] = (digitalRead (IRa2) != 1) ? ( 1 ) : ( 0 );

    RoadBTraffic[0] = (digitalRead (IRb1) != 1) ? ( 1 ) : ( 0 );
    RoadBTraffic[1] = (digitalRead (IRb2) != 1) ? ( 1 ) : ( 0 );

    RoadCTraffic[0] = (digitalRead (IRc1) != 1) ? ( 1 ) : ( 0 );
    RoadCTraffic[1] = (digitalRead (IRc2) != 1) ? ( 1 ) : ( 0 );

    RoadDTraffic[0] = (digitalRead (IRd1) != 1) ? ( 1 ) : ( 0 );
    RoadDTraffic[1] = (digitalRead (IRd2) != 1) ? ( 1 ) : ( 0 );

    int sum1 = RoadATraffic[0] + RoadATraffic[1];
    int sum2 = RoadBTraffic[0] + RoadBTraffic[1];
    int sum3 = RoadCTraffic[0] + RoadCTraffic[1];
    int sum4 = RoadDTraffic[0] + RoadDTraffic[1];

    Serial.print(current_route);
    Serial.print('\n');
    Serial.print(jam_ind);
    Serial.print('\n');
    Serial.print('\n');

    change_route(jam[current_route]);
    display();
      
    if (sum1 >= sum2 && sum1 >= sum3 && sum1 >= sum4) {     // Road A Jam
      if (jam[current_route] == 'a' && counter == 1) {
        increase_jam_ind();
        jam[jam_ind] = 'a';
      } else if (jam[current_route] != 'a' && jam[jam_ind] != 'a') {
        increase_jam_ind();
        jam[jam_ind] = 'a';
      }
    }

    if (sum2 >= sum1 && sum2 >= sum3 && sum2 >= sum4) { // Road B Jam
      if (jam[current_route] == 'b' && counter == 1) {
        increase_jam_ind();
        jam[jam_ind] = 'b';
      } else if (jam[current_route] != 'b' && jam[jam_ind] != 'b') {
        increase_jam_ind();
        jam[jam_ind] = 'b';
      }
    }
    
    if (sum3 >= sum1 && sum3 >= sum2 && sum3 >= sum4) { // Road C Jam
      if (jam[current_route] == 'c' && counter == 1) {
        increase_jam_ind();
        jam[jam_ind] = 'c';
      } else if (jam[current_route] != 'c' && jam[jam_ind] != 'c') {
        increase_jam_ind();
        jam[jam_ind] = 'c';
      }
    }
      
    if (sum4 >= sum1 && sum4 >= sum2 && sum4 >= sum3) { // Road D Jam
      if (jam[current_route] == 'd' && counter == 1) {
        increase_jam_ind();
        jam[jam_ind] = 'd';
      } else if (jam[current_route] != 'd' && jam[jam_ind] != 'd') {
        increase_jam_ind();
        jam[jam_ind] = 'd';
      }
    }  
}

void display() {
  for (int h = 1; h<10000; h++){
    sevseg.setNumber(counter);
    sevseg.refreshDisplay();  
  }
  if (counter <= 0) {
    counter = 5;
    current_route++;
  }

  if (current_route > 15) { 
    current_route = 0;
  }
  
  counter--;
}

void change_route(char route) {
  switch (route) {
    case 'a':
      digitalWrite(LEDGa, HIGH);
      digitalWrite(LEDRa, LOW);
    
      digitalWrite(LEDGb, LOW);
      digitalWrite(LEDRb, HIGH);
    
      digitalWrite(LEDGc, LOW);
      digitalWrite(LEDRc, HIGH);
    
      digitalWrite(LEDGd, LOW);
      digitalWrite(LEDRd, HIGH);
      break;

    case 'b':
      digitalWrite(LEDGa, LOW);
      digitalWrite(LEDRa, HIGH);
    
      digitalWrite(LEDGb, HIGH);
      digitalWrite(LEDRb, LOW);
    
      digitalWrite(LEDGc, LOW);
      digitalWrite(LEDRc, HIGH);
    
      digitalWrite(LEDGd, LOW);
      digitalWrite(LEDRd, HIGH);
      break;

    case 'c':
      digitalWrite(LEDGa, LOW);
      digitalWrite(LEDRa, HIGH);
    
      digitalWrite(LEDGb, LOW);
      digitalWrite(LEDRb, HIGH);
    
      digitalWrite(LEDGc, HIGH);
      digitalWrite(LEDRc, LOW);
    
      digitalWrite(LEDGd, LOW);
      digitalWrite(LEDRd, HIGH);
      break;

    case 'd':
      digitalWrite(LEDGa, LOW);
      digitalWrite(LEDRa, HIGH);
    
      digitalWrite(LEDGb, LOW);
      digitalWrite(LEDRb, HIGH);
    
      digitalWrite(LEDGc, LOW);
      digitalWrite(LEDRc, HIGH);
    
      digitalWrite(LEDGd, HIGH);
      digitalWrite(LEDRd, LOW);
      break;
  }
}

void increase_jam_ind() {
  jam_ind++;
  if (jam_ind > 15) {
    jam_ind = 0;
  }
}

How to use the fgets() function in C

#include <stdio.h>

int main(){
  char str[20];
  
  fgets(str, 20, stdin); // read from stdin
  puts(str); // print read content out to stdout
  
  // open the file
  FILE *f = fopen("file.txt" , "r"); 
  
  // if there was an error
  if(f == NULL){
    perror("Error opening file"); // print error
    return(-1); 
  }
  // if there was no error
  else{ 
    fgets(str, 20, f); // read from file
    puts(str); // print read content out to stdout
  }
  
  fclose(f); // close file
  
  return(0);
}

Prying “.R” Script Files Away from Xcode (et al) on macOS | rud.is

sdk_path="/Library/Developer/CommandLineTools/SDKs"

#c #c++ #wrapper

Was ist ein Wrapper ? | C++ Community

class Wrapper
{
 private:
  CLib *lib;

 public:
  Wrapper() { lib = lib_init(); } // Lib initialisieren
  ~Wrapper() { lib_cleanup(&init); } // Lib freigeben

  std::string DoSomething() 
  { 
    char *cstr = lib_get_str(); // String anfordern (malloc!)

    std::string s = str;  // in std::string kopieren

    lib_free_str(cstr); // String freigeben (free)

    return s; // std::string zurückgeben. Alles easy.
  }
};

#c #c++ #wrapper

What is the meaning of a C++ Wrapper Class? - Stack Overflow

class int_ptr_wrapper
{
public:
    int_ptr_wrapper(int value = 0) :
    mInt(new int(value))
    {}

    // note! needs copy-constructor and copy-assignment operator!

    ~int_ptr_wrapper()
    {
        delete mInt;
    }

private:
    int* mInt;
};

LAB_EXAM

#include<stdio.h>
typedef struct student{
    int roll;
    char name[100];
    int marks[3];
}st;
void takeinput(st candidate[]){
     for(int i=0;i<5;i++){
        printf("\nFor student %d\n",i+1);
        printf("Enter the following details\n");
        printf("roll:");
        scanf("%d",&candidate[i].roll);
        printf("name:");
        scanf("%s",candidate[i].name);
        for(int j=0;j<3;j++){
            printf("marks in subject %d:",j+1);
            scanf("%d",&candidate[i].marks[j]);
        }
     }
}
void printinput(st candidate[]){
    printf("The details of all the students are as follows\n");
    for(int i=0;i<5;i++){
        printf("\nroll no:%d\nname:%s\n",candidate[i].roll,candidate[i].name);
        for(int j=0;j<3;j++){
            printf("marks in subject %d:%d\n",j+1,candidate[i].marks[j]);
        }
    }
}
void average_st_mks(st candidate[]){
    printf("Enter the serial number(1-5) of the student whose average marks to be known\n");
    int no;
    scanf("%d",&no);
    int sum=0;
    for(int i=0;i<3;i++) sum+=candidate[no-1].marks[i];
    float avg=(float)sum/3;
    printf("The average marks candidate bearing roll:%d is %.2f\n",candidate[no-1].roll,avg);
}
void average_subj_mks(st candidates[]){
    printf("Enter the serial number(1-3) of the subject whose average is to be known\n");
    int subject_number;
    scanf("%d",&subject_number);
    int sum=0;
    for(int i=0;i<5;i++){
        sum+=candidates[i].marks[subject_number-1];
    }
    float avg=(float)sum/5;
    printf("The average score of students in subject no:%d is %.2f\n",subject_number,avg);
}
void swap(st *candidate){
    printf("Enter the serial number(1-5) of student whose subject marks are to be swapped\n");
    int i;
    scanf("%d",&i);
    printf("Enter the serial number(1-3) of two subjects whose marks to be swapped\n");
    int a,b;
    scanf("%d%d",&a,&b);
    int temp=candidate[i-1].marks[a-1];
    candidate[i-1].marks[a-1]=candidate[i-1].marks[b-1];
    candidate[i-1].marks[b-1]=temp;
}
void print_mks_student(st candidate[]){
    printf("Enter the serial number(1-5) of the student you want to print marks\n");
    int n;
    scanf("%d",&n);
    for(int i=0;i<3;i++){
        printf("subject %d: %d mks\n",i+1,candidate[n-1].marks[i]);
    }
}
void upp_to_low(st candidate[]){
    printf("Enter the serial number(1-5) of student you want to convert name to lowercase\n");
    int n;
    scanf("%d",&n);
    int i=0;
    do{
        char ch=candidate[n-1].name[i];
        if(ch>=65 && ch<=90) candidate[n-1].name[i]=ch+32;
        i++;
    }while(candidate[n-1].name[i]!='\0');
    printf("student name changed to %s\n",candidate[n-1].name);
}
int main(){
    st candidate[5];
    int flag=1;
    char choice;
    do{
        printf("\nEnter the choice from the menu as per mentioned in the question paper\n");
        printf("The choice should be between a-g(lowercase)\nEnter any other character to stop the program\n");
        scanf(" %c",&choice);
        switch(choice){
        case 'a':takeinput(candidate);
        break;
        case 'b':printinput(candidate); 
        break;
        case 'c':average_st_mks(candidate);
        break;
        case 'd':average_subj_mks(candidate);
        break;
        case 'e':swap(candidate);
        break;
        case 'f':print_mks_student(candidate);
        break;
        case 'g':upp_to_low(candidate);
        break;
        default: flag=0;
        }
    }while(flag==1);
    return 0;
}

Debug Challenge!

#include<stdio.h>
#define take(n) scanf("%d",&n);
#define rep(i,a,b) for(int i=a;i<b;i++)
void add_10(int n){
    printf("Enter a number\n");
    int x;
    take(x);
    printf("%d+%d=%d\n",n,x,n+x);
}
void multiply_10(int n){
    printf("Enter a number\n");
    int x;
    take(x);
    printf("%d*%d=%d\n",n,x,n*x);
}

int main()
{
    int n=10;
    char choice;
    int flag=0;
    do{
        printf("Enter your choice either a or b, any other to exit\n");
        scanf("%c",&choice);
        switch(choice){
            case 'A':
            case 'a': add_10(n);
            break;
            case 'B':
            case 'b': multiply_10(n);
            break;
            default: flag=1;
        }
    }while(flag==0);
return 0;
}

C Program to Implement Queue Using Two Stacks - Sanfoundry

https://www.sanfoundry.com/c-program-implement-queue-using-two-stacks/

rectangle area calculator

#include <stdio.h>
int main()
{
	int lenght,bredth;
	int end;
	printf("what is the lenght of the rectangle \n");
	scanf("%d",&lenght);
	printf("what is the bredth of rectangle \n");
    scanf("%d",&bredth);
    printf("area of rectangle = %d \n",lenght*bredth);
    printf("Programe By Aaryan \n");
    printf("press any key to proseed");
    scanf("%d",&end);
	return 0;
}

KSA - Key Scheduling Algorithm

j = 0;
S = range(256)
for i in range(256):
    j = (j + S[i] + K[i%n]) % 256
    S[i], S[j] = S[j], S[i]

RC4 - Algoritmo central

i = 0
j = 0
for b in range(m):
    i = (i + 1) % 256
    j = (j + S[i]) % 256
    S[i], S[j] = S[j], S[i]
    KS[b] = S[(S[i] + S[j]) % 256]

Salsa20 función central

#define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
void salsa20_word_specification(uint32 out[16],uint32 in[16])
{
    int i;
    uint32 x[16];
    for (i = 0;i < 16;++i) x[i] = in[i];
    for (i = 20;i > 0;i -= 2) {
        x[ 4] ^= R(x[ 0]+x[12], 7);  x[ 8] ^= R(x[ 4]+x[ 0], 9);
        x[12] ^= R(x[ 8]+x[ 4],13);  x[ 0] ^= R(x[12]+x[ 8],18);
        x[ 9] ^= R(x[ 5]+x[ 1], 7);  x[13] ^= R(x[ 9]+x[ 5], 9);
        x[ 1] ^= R(x[13]+x[ 9],13);  x[ 5] ^= R(x[ 1]+x[13],18);
        x[14] ^= R(x[10]+x[ 6], 7);  x[ 2] ^= R(x[14]+x[10], 9);
        x[ 6] ^= R(x[ 2]+x[14],13);  x[10] ^= R(x[ 6]+x[ 2],18);
        x[ 3] ^= R(x[15]+x[11], 7);  x[ 7] ^= R(x[ 3]+x[15], 9);
        x[11] ^= R(x[ 7]+x[ 3],13);  x[15] ^= R(x[11]+x[ 7],18);
        x[ 1] ^= R(x[ 0]+x[ 3], 7);  x[ 2] ^= R(x[ 1]+x[ 0], 9);
        x[ 3] ^= R(x[ 2]+x[ 1],13);  x[ 0] ^= R(x[ 3]+x[ 2],18);
        x[ 6] ^= R(x[ 5]+x[ 4], 7);  x[ 7] ^= R(x[ 6]+x[ 5], 9);
        x[ 4] ^= R(x[ 7]+x[ 6],13);  x[ 5] ^= R(x[ 4]+x[ 7],18);
        x[11] ^= R(x[10]+x[ 9], 7);  x[ 8] ^= R(x[11]+x[10], 9);
        x[ 9] ^= R(x[ 8]+x[11],13);  x[10] ^= R(x[ 9]+x[ 8],18);
        x[12] ^= R(x[15]+x[14], 7);  x[13] ^= R(x[12]+x[15], 9);
        x[14] ^= R(x[13]+x[12],13);  x[15] ^= R(x[14]+x[13],18);
    }
    for (i = 0;i < 16;++i) out[i] = x[i] + in[i];
}

Error de gets

#include <stdio.h>
int main () {
    char username[8];
    int allow = 0;
    printf external link("Enter your username, please: ");
    gets(username);
    if (grantAccess(username)) {
        allow = 1;
    }
    if (allow != 0) {
        privilegedAction();
    }
    return 0;
}

Error de tmp

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
 
#define MY_TMP_FILE "/tmp/file.tmp"
 
 
int main(int argc, char* argv[])
{
    FILE * f;
    if (!access(MY_TMP_FILE, F_OK)) {
        printf external link("File exists!\n");
        return EXIT_FAILURE;
    }
    tmpFile = fopen(MY_TMP_FILE, "w");
 
    if (tmpFile == NULL) {
        return EXIT_FAILURE;
    }
 
    fputs("Some text...\n", tmpFile);
 
    fclose(tmpFile);
 
    return EXIT_SUCCESS;
}

4.Fractional Knapsack

Save snippets that work from anywhere online with our extensions

Comments

More like this

ADA-LAB

Browse more snippets >>

4.Fractional Knapsack

Save snippets that work from anywhere online with our extensions

Comments

More like this

ADA-LAB

Browse more snippets >>

Embed code snippet