동적 기획 01 가방 기록

1146 단어 동적 기획
01 가방은 동적 기획의 한 유형으로 그 주요한 형식은 다음과 같다.
1、모든 종류 아이템 종류마다 1 개
2、한 번에 하나만 수령 가능하며 아이템 분할불가
3、찾거나 안 찾거나 (그래서 01가방이라고 하는데 이 두 가지 상황만 있음)
4、가방의 용량이 부족한 전제에서 가능한 한 많은 최대 가치의 아이템을 장착
가방의 용량은 V이고 i번째 아이템의 무게는weigh[i]에 대응하는 가치는price[i]이다.용량이 j(j의 최대치가 가방의 용량)인 가방이 장착할 수 있는 최대 가치는 dp[j]
n은 모든 물품의 개수이다. 우리는 첫 번째 데이터부터 시작한다. 이 물품의 무게가 weigh[1]이면 우리는 weigh[1]보다 큰 모든 가방을 첫 번째 물품(즉 dp[V]부터
dp[weigh[1]) 이때 모든 weigh[1] 무게보다 큰 가방은 첫 번째 아이템에 장착됩니다.
다음에 우리는 두 번째 아이템을 장착합니다. 이때 마찬가지로 우리는 모든 용량이 weigh[2]보다 큰 가방에 두 번째 아이템을 장착해야 합니다. 그러나 첫 번째 아이템을 장착할 때 일부 가방은 이미 장착했습니다.
첫 번째 물품인데 어떡하지?아래의 몇 가지 상황으로 나누다
1. 첫 번째 물품을 넣은 후 용량이 부족하여 두 번째 물품을 넣을 수 없고 첫 번째 물품의 가치가 두 번째 물품보다 크면 두 번째 물품을 넣지 않는다
2. 첫 번째 물품을 넣은 후 남은 용량이 부족하여 두 번째 물품을 넣었을 때 첫 번째 물품의 가치가 두 번째 물품보다 크지 않으면 두 번째 물품을 넣고 첫 번째 물품을 꺼낸다(당연히 프로그램에서
중 첫 아이템 픽업으로 즉시 커버 가능)
3、첫 번째 아이템을 장착한 후 용량이 두 번째 아이템을 장착할 수 있다면 두 아이템을 가방에 함께 장착
코드 구현:
for(i=0;i<n;i++)
{
	for(j=V;j>=weigh[i];j++)//       weigh[i]        
	{
		dp[j]=max(dp[j],dp[j-weigh[i]]+price[i]);
	}
}

이것으로 유추하다
큰 신은 분출하지 마라
js 현재 화면 캡 처 를 실현 하고 그림 으로 저장
갈 수 있어서 너무 좋아요.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage