Knapsack backtracking

-

 #include<stdio.h>


void knapsack(int, int[], int[], int);

void backtrack(int, int, int[], int[], int, int*, int*, int[]);


int main()

{

    int capacity, n;

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

    scanf("%d", &n);


    int weights[n], profits[n];

    printf("Enter weights of the items: ");

    for (int i = 0; i < n; i++) {

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

    }

    printf("Enter profits of the items: ");

    for (int i = 0; i < n; i++) {

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

    }

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

    scanf("%d", &capacity);


    knapsack(n, weights, profits, capacity);


    return 0;

}


void knapsack(int n, int weights[], int profits[], int capacity)

{

    int maxProfit = 0;

    int currentWeight = 0, currentProfit = 0;

    int included[n]; // Track items included in the knapsack

    int bestSet[n];  // Track the best combination of items

    for (int i = 0; i < n; i++) {

        included[i] = 0;

        bestSet[i] = 0;

    }


    backtrack(0, n, weights, profits, capacity, &maxProfit, &currentWeight, included);


    printf("Max profit is: %d\n", maxProfit);

    printf("Items included in the knapsack: ");

    for (int i = 0; i < n; i++) {

        if (included[i]) {

            printf("%d ", i + 1);

        }

    }

    printf("\n");

}


void backtrack(int i, int n, int weights[], int profits[], int capacity, int *maxProfit, int *currentWeight, int included[])

{

    if (i == n) { // Reached the end of items

        int currentProfit = 0;

        for (int j = 0; j < n; j++) {

            if (included[j]) {

                currentProfit += profits[j];

            }

        }

        if (currentProfit > *maxProfit) {

            *maxProfit = currentProfit;

        }

        return;

    }


    // Exclude the current item

    backtrack(i + 1, n, weights, profits, capacity, maxProfit, currentWeight, included);


    // Include the current item if it fits

    if (*currentWeight + weights[i] <= capacity) {

        included[i] = 1;

        *currentWeight += weights[i];

        backtrack(i + 1, n, weights, profits, capacity, maxProfit, currentWeight, included);

        *currentWeight -= weights[i]; // Backtrack

        included[i] = 0;             // Reset the inclusion state

    }

}


Comments

Post a Comment

Popular posts from this blog

AVL Trees

-
#include <stdio.h> #include <stdlib.h> // Structure to represent a node in the AVL tree struct Node {     int key;     struct Node* left;     struct Node* right;     int height; }; // Function to get the height of the node int height(struct Node* N) {     if (N == NULL)         return 0;     return N->height; } // Function to get the maximum of two integers int max(int a, int b) {     return (a > b) ? a : b; } // Helper function that allocates a new node with the given key struct Node* newNode(int key) {     struct Node* node = (struct Node*)malloc(sizeof(struct Node));     node->key = key;     node->left = NULL;     node->right = NULL;     node->height = 1; // New node is initially added at leaf     return(node); } // Right rotate subtree rooted with y struct Node* rightRotate(struct Node* y) {     ...
Read more

BFS Matrix

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 int adj[MAX][MAX];   int state[MAX];      int queue[MAX], front = -1, rear = -1;  void create_graph(int n, int gtype); void BF_Traversal(int n); void BFS(int v, int n); void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() {     int n, gtype;          printf("Enter 1 for undirected graph and -1 for directed graph: ");     scanf("%d", &gtype);     printf("Enter the number of vertices: ");     scanf("%d", &n);          create_graph(n, gtype);          BF_Traversal(n);          return 0; } void create_graph(int n, int gtype) {     int max_edges, src, dest;          if (gtype == 1)         max_edges = (n * (n - 1)) /...
Read more

BFS List

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 struct Node { int vertex; struct Node* next; }; int queue[MAX],front=-1,rear=-1; int state[MAX]; struct Node* adj[MAX]; void create_graph(int n,int gtype); void insert_queue(int v); int delete_queue(); int isEmpty_queue(); void BFT(int n); void BFS(int start,int n); void add_edge(int src,int dest); struct Node* create_node(int v); int main() { int gtype,n; printf("Enter 1 for undirected graph and -1 for directed graph:"); scanf("%d",&gtype); printf("Enter the number of vertices:"); scanf("%d",&n); create_graph(n,gtype); BFT(n); return 0; } void create_graph(int n,int gtype) { int max_edges,src,dest; if(gtype==1) max_edges=(n*(n-1))/2; else if(gtype==-1) max_edges=(n*(n-1)); for(int i=0;i<n;i++) adj[i]=NULL; for(int i=0;i<max_edges;i++) { printf("Enter edge %d (press -1 and -1 to quit):...
Read more