Untitled

GamerBhai02

Jun 3rd, 2025 (edited)

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

text 5.19 KB | None | 0 0

raw download clone embed print report

def fractional_knapsack(capacity, items):
items.sort(key=lambda x: x[0]/x[1], reverse=True)
max_val = 0.0
for value, weight in items:
if capacity >= weight:
max_val += value
capacity -= weight
else:
return round(max_val + value * (capacity / weight), 6)
return round(max_val, 6)
n, w = map(int, input().split())
item_list = list(map(int, input().split()))
items = [(item_list[i],item_list[i+1]) for i in range(0, len(item_list), 2)]
print(format(fractional_knapsack(w, items),".6f"))
def floyd_warshall(n,edges):
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u,v,w in edges:
dist[u-1][v-1] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
n, e = int(input()), int(input())
edges = [tuple(map(int, input().split())) for _ in range(e)]
for row in floyd_warshall(n,edges):
print(*["INF" if x == float('inf') else x for x in row],"")
def warshall_algorithm(graph, n):
# Only this function for codetantra
for k in range(n):
for i in range(n):
for j in range(n):
graph[i][j] |= graph[i][k] and graph[k][j]
return graph
# Till here
n = int(input().strip())
graph = [list(map(int, input().split())) for _ in range(n)]
transitive_closure = warshall_algorithm(graph, n)
for row in transitive_closure:
print(" ".join(map(str, row)))
def count_topo_sorts(v,edges):
from collections import defaultdict
adj = defaultdict(list)
in_degree = [0]*V
for u,v in edges:
adj[u].append(v)
in_degree[v] += 1
visited = [False]*V
count = [0]
def backtrack(path):
if len(path) == V:
count[0] += 1
return
for i in range(V):
if not visited[i] and in_degree[i]==0:
visited[i] = True
for neighbor in adj[i]:
in_degree[neighbor] -= 1
backtrack(path+[i])
visited[i] = False
for neighbor in adj[i]:
in_degree[neighbor] += 1
backtrack([])
return count[0]
V = int(input())
E = int(input())
edges = [tuple(map(int, input().split())) for _ in range(E)]
print(count_topo_sorts(V, edges))
def subset_sum(arr,N,target_sum):
for i in range(len(arr)):
for j in range(len(arr)):
if arr[i]+arr[j]==target_sum:
return True
return False
N=int(input())
arr=list(map(int, input().split()))
target_sum=int(input())
print(subset_sum(arr,N,target_sum))
def is_safe(board, row, col, N):
for i in range(row):
if board[i][col] == 1:
return False
i, j = row-1, col-1
while i>=0 and j>=0:
if board[i][j]==1:
return False
i-=1
j-=1
i, j = row-1, col+1
while i>=0 and j<N:
if board[i][j]==1:
return False
i-=1
j+=1
return True
def solve_n_queens_util(board, row, N):
if row==N:
return True
for col in range(N):
if is_safe(board,row,col,N):
board[row][col]=1
if solve_n_queens_util(board,row+1,N):
return True
board[row][col] = 0
return False
def solve_n_queens(N):
board = [[0 for _ in range(N)] for _ in range(N)]
if solve_n_queens_util(board,0,N):
print(f"Solution for {N}-Queens problem:")
for row in board:
print("".join(str(cell)+"\t" for cell in row))
else:
print(f"No solution exists for {N}-Queens problem")
N = int(input("value of N: "))
solve_n_queens(N)
def isSafe(board, row, col):
#horizantal
for j in range(len(board)):
if board[row] [j]==1:
return False
#vertical
for i in range(len(board)):
if board[i][col]==1:
return False
#diagonal left
i=row
j=col
while(i>=0 and j>=0):
if board[i][j]==1:
return False
i-=1
j-=1
#diagonal right
i=row
j=col
while(i>=0 and j<len(board)):
if board[i][j]==1:
return False
i-=1
j+=1
return True
def nQueens (board, row, solutions):
n=len(board)
if row==n:
solutions.append ([row[:] for row in board])
return
#column iteration
for j in range(n):
if isSafe(board, row, j):
board[row][j]=1
nQueens (board, row+1, solutions)
board[row][j]=0
def print_board(board):
for row in board:
print('\t'.join(map(str,row))+'\t')
def main():
n=int(input("value of N: "))
if n==2 or n==3:
print(f"No solution exists for {n}-Queens problem")
return
board=[[0 for i in range(n)] for i in range(n)]
solutions=[]
nQueens(board, 0, solutions)
print(f"Solution for {n}-Queens problem:")
print_board(solutions[0])
if name ==' main ':
main()

Add Comment

Please, Sign In to add comment