dp배

import sys
input = sys.stdin.readline
n=list(map(int,input().split()))
goal=[]
li=[] #조합이 들어갈 곳
lit=[]
a=n[0]
m=n[1]
count=0
#lit=[(a,b),(c,d),(e,f),(g,h)]
for i in range(a):
    lit.append(tuple(map(int,input().split())))

def All(r,start=0):
    global count
    if start==len(lit)+1 :
        return

    if len(li)==r:
        goal.append(li[:])
        count+=1
        return
    
    for j in range(start,len(lit)):
        li.append(lit[j])
        All(r,j+1)
        li.pop()


for i in range(1,len(lit)+1): #nCi
    All(i)
    li=[]

#print(goal)
print(count)

설마 weight+value 계속 되냐고 물어보는 게 중복? 뭐지 그럼 모든 경우의 조합을 다 저장해서 그 중 조건을 만족시키는 걸 고르는 건가
일단 위 코드는 모든 경우의 수 조합을 구하는 거
터음 조건문 중요 start가 len(lit)+1이면 return

https://soniacomp.medium.com/%EA%B8%B0%EC%88%A0%EB%A9%B4%EC%A0%91-%EC%9E%AC%EA%B7%80-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-5bf7a7c0b97e

https://jeonyeohun.tistory.com/86

이거랑 자구 최근에 배운 거랑ㄴ 비슷하지않나

다익스트라?? 그 최단이어야 저장해주고

https://seungjuitmemo.tistory.com/101
0-1 knapsack은 그리디로 풀 수 없고 디피 써야된다는데 0-1knapsack이 풀고있는 평범한 배낭 문제

https://sskl660.tistory.com/88

dp를 잘 풀고싶어요. ㄱ
https://www.acmicpc.net/board/view/22717