# 물건 수 N, 최대 배낭 무게 W
N = 4
W = 7
weights = [6, 4, 3, 5]   # 각 물건의 무게
values = [13, 8, 6, 12]  # 각 물건의 가치

# dp[i][w] = i번째 물건까지 고려했을 때, 무게 w로 만들 수 있는 최대 가치
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):  # i번째 물건까지 고려
    for w in range(W + 1):  # 무게 w에 대해서
        if weights[i-1] > w:
            # 현재 물건 무게가 가방보다 크면, 못 담음 → 이전값 그대로
            dp[i][w] = dp[i-1][w]
        else:
            # 담지 않을 경우 vs 담을 경우 중 최대 가치 선택
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])

print("최대 가치:", dp[N][W])

# 물건 수 N, 최대 배낭 무게 W
N = 3
W = 10
weights = [3, 4, 5]
values = [30, 50, 60]

# dp[w] = 무게 w일 때 얻을 수 있는 최대 가치
dp = [0] * (W + 1)

for i in range(N):  # 각 물건에 대해
    for w in range(weights[i], W + 1):  # 그 무게부터 끝까지
        # 현재 무게 w일 때, i번 물건을 하나 더 담는 경우 고려
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

print("최대 가치:", dp[W])

W = 50  # 배낭의 최대 용량
items = [(60, 10), (100, 20), (120, 30)]  # (가치, 무게) 튜플 리스트

# 가치 밀도(value/weight) 기준으로 내림차순 정렬
items.sort(key=lambda x: x[0]/x[1], reverse=True)

total_value = 0.0  # 누적된 가치

for value, weight in items:
    if W >= weight:
        # 통째로 담을 수 있으면 담기
        total_value += value
        W -= weight
    else:
        # 일부만 담아야 하면 비례해서 담기
        total_value += value * (W / weight)
        break  # 배낭이 가득 찼으므로 종료

print("최대 가치:", total_value)