12865 평범한 배낭

chi·2023년 5월 9일

백준

목록 보기

5/20

n=list(map(int,input().split()))
a=n[0] #몇 개
m=n[1] #최대 무게
li=[]
lit=[]
#lit=[(a,b),(c,d),(e,f),(g,h)]
for i in range(a):
    lit.append(tuple(map(int,input().split())))
weightnow=0 #현재 무게


def additem(start=0):
    global weightnow
    
    for i in range(start,len(lit)): #조합
        weight=lit[i][0]
        if (weightnow+weight)<=m: #더해도 괜찮으면
            weightnow+=weight
            additem(i+1)
        else: #안 되면
            li.append(weightnow) #결과 집어넣어주고

    return

additem()
print(li)

이렇게 하면 예를 들어 최대 무게 7을 앞두고
1 2
3 4
2 5
이렇게 할 때

1+3+2

중복 저장됨 6이

개쳐망한 코드

n=list(map(int,input().split()))
a=n[0] #몇 개
m=n[1] #최대 무게
li=[]
lit=[]
#lit=[(a,b),(c,d),(e,f),(g,h)]
for i in range(a):
    lit.append(tuple(map(int,input().split())))
weightnow=0 #현재 무게
valuenow=0

def additem(start=0):
    global weightnow
    global valuenow
    
    for i in range(start,len(lit)): #조합 (1,2),(3,4),(2,5)
        weight=lit[i][0]
        value=lit[i][1]
        if (weightnow+weight)<=m: #더해도 괜찮으면
            weightnow+=weight
            valuenow+=value
            if i!=len(lit):
                additem(i+1)
                      
        else: #안 되면
            return
            
    li.append((weightnow,valuenow)) #결과 집어넣어주고

additem()
print(li)

의사코드

def additem(start=0):
    global weightnow
    global valuenow
    
    if 지금이 딱이면 더 추가하면 ㅈ되면:
        저장
        return

    else:
        추가해 무게건 가치건
        재귀해

개쳐망ㄴ

n=list(map(int,input().split()))
a=n[0] #몇 개
m=n[1] #최대 무게
li=[]
lit=[]
#lit=[(a,b),(c,d),(e,f),(g,h)]
for i in range(a):
    lit.append(tuple(map(int,input().split())))
weightnow=0 #현재 무게
valuenow=0

def additem(start=0):
    global weightnow
    global valuenow
    
    if 지금이 딱이면 더 추가하면 ㅈ되면:  #아오 여기 어떻게 할 건데 ㅅㅂ
        li.append((weightnow,valuenow))
        return

    else:
        for i in range(start,len(lit)):
            weight=lit[i][0]
            value=lit[i][1]
            if (weightnow+weight)<=m: #더해도 괜찮으면
                weightnow+=weight
                valuenow+=value
                if i!=len(lit):
                    additem(i+1)
            
additem()
print(li)

준성공 일단 조합 구함

부분 코드

def additem(start=0):
    global weightnow
    if start==len(lit): #역시 이 경우를 따로 챙겨줬어야 됐다!!!!!!!!!예외처리???
        li.append(weightnow)
        return

    for i in range(start,len(lit)): #조합
        weight=lit[i][0]
        if (weightnow+weight)<=m: #더해도 괜찮으면
            weightnow+=weight
            additem(i+1) #근데 이러면 start가 마지막일 때 언제 값 저장할 거임
            weightnow-=weight
        else: #안 되면
            li.append(weightnow) #결과 집어넣어주고
            
    return

예외처리

완성인데 메모리 초과

n=list(map(int,input().split()))
a=n[0] #몇 개
m=n[1] #최대 무게
li=[] #무게 조합이 들어갈 곳
va=[] #가치 조합이 들어갈 곳
lit=[]
#lit=[(a,b),(c,d),(e,f),(g,h)]
for i in range(a):
    lit.append(tuple(map(int,input().split())))
weightnow=0 #현재 무게
valuenow=0


def additem(start=0):
    global weightnow, valuenow

    if start==len(lit): #역시 이 경우를 따로 챙겨줬어야 됐다!!!!!!!!!예외처리???
        li.append(weightnow)
        va.append(valuenow)
        return

    for i in range(start,len(lit)): #조합
        weight=lit[i][0]
        value=lit[i][1]
        if (weightnow+weight)<=m: #더해도 괜찮으면
            weightnow+=weight
            valuenow+=value
            additem(i+1) #근데 이러면 start가 마지막일 때 언제 값 저장할 거임
            weightnow-=weight
            valuenow-=value
        else: #안 되면
            li.append(weightnow) #결과 집어넣어주고
            va.append(valuenow)
            
    return

additem()
#print(li)
#print(va)
print(max(va))

무게는 필요없으니까 빼야지 li만 빼면 되려나

시간 초과...

굴러가긴하는데 sys 불러도 여전히 시간초과

import sys
input = sys.stdin.readline
n=list(map(int,input().split()))
a=n[0] #몇 개
m=n[1] #최대 무게
va=[] #가치 조합이 들어갈 곳
lit=[]
#lit=[(a,b),(c,d),(e,f),(g,h)]
for i in range(a):
    lit.append(tuple(map(int,input().split())))
weightnow=0 #현재 무게
valuenow=0


def additem(start=0):
    global weightnow, valuenow

    if start==len(lit): #역시 이 경우를 따로 챙겨줬어야 됐다!!!!!!!!!예외처리???
        va.append(valuenow)
        return

    for i in range(start,len(lit)): #조합
        weight=lit[i][0]
        value=lit[i][1]
        if (weightnow+weight)<=m: #더해도 괜찮으면
            weightnow+=weight
            valuenow+=value
            additem(i+1) #근데 이러면 start가 마지막일 때 언제 값 저장할 거임
            weightnow-=weight
            valuenow-=value
        else: #안 되면
            va.append(valuenow)
            
    return

additem()
#print(li)
#print(va)
print(max(va))

리스트라서 그런가? for을 써서?
어떤 사람은 백트래킹으로 했더니 시간 초과가 나서 DP (Dynamic programming) 동적 프로그래밍으로 풀었다는데..

아니 근데 여기서 했던 거 또 구하고 또 구하고를 언제 했다고 그럼?? 재귀로도 ㄱㄴ하지 않음?