Knapsack problem using Greedy technique

 

Algorithm:

          Algorithm GreedyKnapsack(m,n)

{

for i:=1 to n do x[i] :=0.0; U := m;

for i:= 1 to n do

{

if w[i]> U)then break; 

X[i] := 1.0; U:=U-w[i];

}

if (i<=n) then x[i] := U/w[i];

}


Source Code:

def knapsack_greedy(values, weights, capacity): n = len(values)

ratios = [(values[i] / weights[i], i) for i in range(n)] 

ratios.sort(reverse=True)

selected_item=[] 

total_value = 0

for ratio, i in ratios:

if weights[i] <= capacity: selected_items.append(i) 

total_value += values[i] capacity -= weights[i]

return selected_items, total_value values = [10, 20, 15, 25, 30]

weights = [5, 7, 3, 9, 2]

capacity = 15

selected_items, total_value = knapsack_greedy(values, weights, capacity) print("Selected items:", selected_items)

print("Total value:", total_value)


Comments

Post a Comment

Popular posts from this blog

2. Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.

Image
 In Cisco Packet Tracer, you can simulate this scenario by configuring access control lists (ACLs) on routers to control the flow of traffic between the networks. Here's a basic example: Procedure  1. **Create the Networks:**    - Place three routers on the workspace and label them R1, R2, and R3.    - Connect the routers as follows:      - Connect R1 to R2 and R3.      - Connect R2 to R3.    - Assign IP addresses to the router interfaces for each network (N1, N2, N3). 2. **Configure Router ACLs:**    - Access the CLI of each router.    For R1 (assuming FastEthernet interfaces):    ```bash    enable    configure terminal    interface FastEthernet0/0    ip address <N1_IP> <Subnet_Mask>    exit    interface FastEthernet0/1    ip address <N2_IP> <Subnet_Mask>    exit    access-li...
Read more

Kruskal algorithm using greedy technique.

Algorithm: Algorithm Kruskal(E, cost, n, t) { Construct a heap out of the edge costs using Heapify; for i:=1 to n, do parent[i]:=—1; i := O; mincost := 0.0; while ( (i < n — 1) and (heap not empty)) do       { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust; j:=Find(u); k := Find(v); if (j!=k) then        { i:=i+1; t[i, 1] := u; t[i, 2]:=v; mincost := mincost + cost[u, v]; Union(j, k); }                 } if (i != n — 1) then write ("No spanning tree"); else return mincost; } Source Code: def kruskal(E, cost, n): # E is the edge set, cost is the cost matrix, n is the number of vertices T = [] # T is the set of edges in the tree S = [] # S is the set of vertices in the tree while len(T) < n ...
Read more