The Unbounded Knapsack problem challenges us to optimally fill a knapsack with a designated capacity using items characterized by specific weights and values. The objective is to amplify the overall value of the knapsack’s contents. What sets the unbounded variation apart is the absence of constraints on the number of each item. The decision dilemma, determining if a knapsack can achieve or exceed a certain value, is classified as NP-complete. However, the maximization facet of the problem can be tackled in pseudo-polynomial time, courtesy of dynamic programming techniques.
Core Principles and Algorithmic Design
The underlying algorithm’s strength stems from a bottom-up approach. It populates an array that corresponds to the knapsack’s capacity, each index representing the best possible value obtainable for that capacity. The challenge at every step is discerning the optimal item to incorporate, ensuring the resultant knapsack yields maximum value.
Each array cell maintains a connection to its predecessor, signifying the earlier knapsack configuration before the latest item addition. These connections, embedded as pointers within the array cells, guide the algorithm’s progression and lead to the eventual solution. The culmination of the algorithm presents the array’s final cell, symbolizing the pinnacle of value attainable for the designated knapsack capacity.
Implementing the Dynamic Algorithm in C
| #include <stdio.h>#include <stdlib.h> struct knapsack { unsigned int profit; struct knapsack *prev;};typedef struct knapsack Knapsack; int min_weight_item(unsigned int profit, const unsigned int *weights, const unsigned int *profits, size_t len) { int item = -1; for (unsigned int i = 0; i < len; i++) { if (profits[i] == profit) { if (item == -1 || weights[i] < weights[item]) { item = i; } } } return item;} unsigned int unbounded_knapsack(unsigned int capacity, unsigned int *weights, unsigned int *profits, unsigned int *counts, size_t len) { Knapsack *z = (Knapsack *)malloc((capacity + 1) * sizeof(Knapsack)); unsigned int solution; z[0].profit = 0; z[0].prev = NULL; for (unsigned int c = 1; c <= capacity; c++) { z[c].profit = z[c – 1].profit; // start with the previous profit z[c].prev = &z[c – 1]; for (unsigned int i = 0; i < len; i++) { if (weights[i] <= c) { Knapsack *prev = &z[c – weights[i]]; if (prev->profit + profits[i] > z[c].profit) { z[c].profit = prev->profit + profits[i]; z[c].prev = prev; } } } } Knapsack *current = &z[capacity]; while (current && current->prev) { int itemIndex = min_weight_item(current->profit – current->prev->profit, weights, profits, len); if (itemIndex != -1) counts[itemIndex]++; current = current->prev; } solution = z[capacity].profit; free(z); return solution;} void print_knapsack(const unsigned int *counts, const unsigned int *profits, size_t len) { for (unsigned int i = 0; i < len; i++) { if (counts[i] > 0) { printf(“%d x %d\n”, counts[i], profits[i]); } }} int main(void) { unsigned int weights[] = {4, 3, 5, 7, 11}; unsigned int profits[] = {5, 3, 6, 2, 7}; unsigned int counts[5] = {0}; const size_t len = sizeof(weights) / sizeof(unsigned int); const unsigned int capacity = 17; printf(“The maximum profit is %u\n”, unbounded_knapsack(capacity, weights, profits, counts, len)); print_knapsack(counts, profits, len); return 0;} |
Illustrative Example
This section offers a hands-on example that employs the above algorithm, showcasing its real-world applicability.
| …int main(void) { … printf(“The maximum profit is %u\n”, unbounded_knapsack(capacity, weights, profits, counts, len)); …} |
Output:
| The maximum profit is 213 x 51 x 6 |
Comparison Table
| Attributes | Unbounded Knapsack | Regular Knapsack |
|---|---|---|
| Item Repetition | Unlimited | Constrained |
| Solution Approach | Dynamic Programming | Dynamic/Backtracking |
| Computational Complexity | Pseudo-polynomial | Exponential |
Implementing Topological Sort in C
The algorithm for topological sorting is straightforward:
- Choose a vertex with no incoming edges;
- Visit this vertex and then recursively visit all its neighbors. Mark the current vertex as visited;
- Once the vertex and its neighbors are visited, add the vertex to the topological order;
- Repeat the process until all the vertices are visited.
Here’s a simple implementation of the Topological Sort in C using Depth First Search (DFS):
| #include <stdio.h>#include <stdlib.h> #define MAX 10 // Adjacency list nodetypedef struct Node { int vertex; struct Node* next;} Node; // Graph with an adjacency listtypedef struct Graph { int numVertices; Node* adjLists[MAX]; int visited[MAX];} Graph; Node* createNode(int vertex);Graph* createGraph(int vertices);void addEdge(Graph* graph, int src, int dest);void topologicalSort(Graph* graph, int vertex, int* stack, int* top);void printStack(int* stack); int main() { Graph* graph = createGraph(6); addEdge(graph, 5, 2); addEdge(graph, 5, 0); addEdge(graph, 4, 0); addEdge(graph, 4, 1); addEdge(graph, 2, 3); addEdge(graph, 3, 1); int stack[MAX], top = -1; for (int i = 0; i < graph->numVertices; i++) if (!graph->visited[i]) topologicalSort(graph, i, stack, &top); printStack(stack); return 0;} Node* createNode(int vertex) { Node* newNode = malloc(sizeof(Node)); newNode->vertex = vertex; newNode->next = NULL; return newNode;} Graph* createGraph(int vertices) { Graph* graph = malloc(sizeof(Graph)); graph->numVertices = vertices; for (int i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; graph->visited[i] = 0; } return graph;} void addEdge(Graph* graph, int src, int dest) { Node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode;} void topologicalSort(Graph* graph, int vertex, int* stack, int* top) { graph->visited[vertex] = 1; Node* adjList = graph->adjLists[vertex]; Node* temp = adjList; while (temp != NULL) { int connectedVertex = temp->vertex; if (!graph->visited[connectedVertex]) topologicalSort(graph, connectedVertex, stack, top); temp = temp->next; } stack[++(*top)] = vertex;} void printStack(int* stack) { int i = 0; while (stack[i] != -1) { printf(“%d “, stack[i]); i++; } printf(“\n”);} |
In this implementation, we’ve utilized an adjacency list representation for the graph. The topologicalSort function uses DFS to recursively traverse the graph and fill the stack in a topological order.
Conclusion
The Unbounded Knapsack problem, while complex, becomes more approachable through dynamic programming. This exploration in C not only provides a clear understanding of the problem but also equips readers with a robust solution template.