알고리즘 - 가방 문제

완전 가방 과 다 중 가방 부분 에 저 는 제 생각 대로 썼 습 니 다. 문제 가 있 으 면 지적 해 주세요!감사합니다!
가방 문 제 는 동태 계획 에서 비교적 전형 적 인 문제 형 으로 대체적으로 3 가지 01 가방, 완전 가방 과 다 중 가방 으로 나 눌 수 있다.
가방
질문 설명:
n 가지 아 이 템 이 있 습 니 다. 각각 1 개 만 있 습 니 다.제 i 중 아 이 템 의 부 피 는 v i vi vi, 무 게 는 w i wi wi​。일부 물품 을 선택 하여 용량 이 C 인 가방 에 넣 으 면 가방 안의 물품 의 총 부피 가 C 를 초과 하지 않 는 전제 에서 무 게 는 가능 한 한 크다.
2 차원 해법
가장 간단 한 사 고 는 두 개의 상태 dp [i] [j] 를 사용 하여 i 개의 아 이 템 을 담 았 을 때 부피 가 j 인 상황 에서 얻 을 수 있 는 최대 무 게 를 나타 내 는 것 이다.상태 이전 은 다음 과 같 습 니 다: dp [i] [j] = max (dp [i - 1] [j], dp [i - 1] [j - v [i]] + w [i]) 즉 제 i 개 아 이 템 과 같이 장 착 하거나 제 i 개 아 이 템 을 불 러 오지 않 으 면 얻 는 무게 의 비교적 큰 값 입 니 다.

for i in range(1, n+1):
	for j in range(C+1):
		if v[i] < j:
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

일차 해법
2 차원 해법 에서 의 전이 방정식 에 따라 발송 할 수 있 습 니 다. i 번 째 아 이 템 에 장 착 할 때 얻 을 수 있 는 최대 무 게 는 i - 1 에 장 착 할 때 만 관련 되 기 때문에 상태 압축 dp [j] = max (dp [j], dp [j - v [i]] + w [i]) 를 진행 할 수 있 습 니 다.

for i in range(n):
	for j in range(C+1):
		if v[i] < j:
			dp[j] = max(dp[j], dp[j - v[i]] + w[i])

완전 가방
질문 설명:
01 가방 과 유사 하지만, 각 종류의 아 이 템 은 무한 개
해결 방안
상태 이동 방정식 은 01 가방 과 같 습 니 다: dp [j] = max (dp [j], dp [j - v [i]] + w [i])

for j in range(C+1):
	for i in range(n):
		if v[i] < j:
			dp[j] = max(dp[j], dp[j - v[i]] + w[i])

욕심
완전 가방 문제 에서 개수 의 제한 이 없 기 때문에 우 리 는 먼저 밀 도 를 계산 하고 밀도 가 높 은 물건 을 우선 선택 하면 된다. 이렇게 복잡 도 는 동태 계획 보다 훨씬 작다.
3. 다 중 가방
질문 설명:
다 중 가방 은 완전 가방 에 수량 제한 을 더 한 것 으로, i 종 아 이 템 의 수량 은 n i n 입 니 다.i ni​
해결 방안
해결 방법 은 완전 가방 과 비슷 합 니 다. 옮 겨 다 닐 때 남 은 물건 이 있 는 지 판단 하면 dp [j] = max (dp [j], dp [j - v [i]] + w [i])

for j in range(C+1):
	last = -1
	for i in range(n):
		if v[i] < j and n[i]:
			if dp[j] < dp[j - v[i]] + w[i]:
				dp[j] = dp[j - v[i]] + w[i]
				last = i
	if last:
		n[i] -= 1