-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
방문체크 하지 않아도 되나요?
22.03.08 17:35 작성 조회수 210
0
부분집합을 하는 문제라고 판단하여, 부분집합구하기 문제처럼 ch(체크) 리스트 만들어서 풀었는데 답이 안나오네요.. 무엇이 문제일까요? 강의를 보니 체크 리스트 사용하지 않으셨던데... 사용해야하는 것 아닌가요?
추가적인 질문으로, 부분집합과 조합 방식의 차이가 무엇인지 아직까지 잘 이해가 되지 않는데.. 부분집합은 가지치기가 본인 포함 전부 다 되고, 조합은 가지치기가 본인을 제외한 하위 부분만 되는게 맞나요?
부분집합을 조합처럼 구할 수 있고, 조합을 부분집합처럼 구할 수 있나요?
def DFS(L, time, sum):
global res
if time > m:
return
if L == n:
if sum > res:
res = sum
else:
for i in range(n):
if visited[i] == 0:
visited[i] = 1
DFS(i, time+graph[i][1], sum+graph[i][0])
visited[i] = 0
DFS(i, time, sum)
if __name__ == '__main__':
n, m = map(int, input().split())
graph = []
for _ in range(n):
a, b = map(int, input().split())
graph.append([a, b])
visited = [0]*n
res = 0 # 최대 점수
DFS(0, 0, 0)
print(res)
답변을 작성해보세요.
0
김태원
지식공유자2022.03.14
안녕하세요^^
문제를 푼다, 안푼다는 굳이 체크를 하지 않아도 됩니다.
부분집합 코드에서 조합을 구하기는 힘들 것 같습니다. 하지만 조합코드에서 부분집합을 구할 수 있습니다.
답변 1