글 읽기 - 틀렸습니다.... 반례 부탁드립니다.......!

cheonghc7 1년 전 0

dp로 푸는 것보다 백트래킹으로 푸는 풀이가 먼저 떠올라(더 단순무식한 방법이라 그렇겠지만) 백트래킹으로 푼 뒤 dp로 풀어보려 하였으나 백트래킹에서 막히네요...

틀렸습니다 가 뜨는데 반례를 찾아주신다면 정말 감사하겠습니다 ㅜㅜ

주석도 나름 열심히 달아보았습니다..!

import collections
import sys

inputt = sys.stdin.readline
printt = sys.stdout.write

n, k = map(int, inputt().split())
weight = []
value = []
for _ in range(n):
    w, v = map(int, inputt().split())
    weight.append(w)
    value.append(v)

# 특정한 weight로 담을 수 있는 최대의 value를 기록하는 dictionary
weight_value = collections.defaultdict(lambda: -sys.maxsize)
put = [False] * n

# idx 번째 물건을 배낭에 넣을 것인지 말 것인지. (curr_weight = 0, curr_value = 0, idx = 0)에서 시작
def back_track(curr_weight, curr_value, idx):
    # 이전에 curr_weight만큼 담았을 때의 value가 curr_value보다 작다면 업데이트
    if weight_value[curr_weight] < curr_value:
        weight_value[curr_weight] = curr_value
    if idx >= n:
        return
    # idx 번째 물건을 배낭에 넣는 것이 의미 있는지, 가능한지 확인한 후 그러하다면 idx 번째 물건을 담은 뒤 진행
    if weight_value[curr_weight + weight[idx]] <= curr_value + value[idx] and curr_weight + weight[idx] <= k:
        put[idx] = True
        back_track(curr_weight + weight[idx], curr_value + value[idx], idx + 1)
    # idx 번째 물건을 담을 수 있건 없건 간에 담아보지 않고도 진행
    put[idx] = False
    back_track(curr_weight, curr_value, idx + 1)
    return


back_track(0, 0, 0)
print(max(weight_value.values()))

seawon0808 1년 전 0

반례입니다.

입력을 넣었을 때 출력이 없네요.

cheonghc7 1년 전 0

저.. 감사한 마음에 서둘러 돌려 보았는데 입력값이 14개라서 출력이 되지 않는 것 같습니다...! ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다.... 반례 부탁드립니다.......!

cheonghc7 1년 전 0

seawon0808 1년 전 0

cheonghc7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말