【필기】가방 9강-통합판

원판
배낭문제 9강 2.0 알파1 최첨익(Tianyi Cui, a.k.a. dd engi)
배낭9강 학습노트 제1강01배낭9강 학습노트 제2강 완전배낭문제 배낭9강 학습노트 제3강 다중배낭9강 학습노트: 제4강-혼합 3가지 배낭문제 제5강-2차원 비용의 배낭문제 배낭9강 학습노트 제6강-조별 배낭문제 배낭9강 학습노트 제7강 - 의존적배낭문제 제8강-범화 아이템 배낭9강 학습노트 제9강 배낭문제문법의 변화
1.01 가방
N 아이템과 V 용량의 가방이 있습니다.i번째 아이템을 넣는 데 소모되는 공간은 Ci이고, 얻는 가치는 Wi다.어떤 아이템을 가방에 넣으면 가치 총화를 최대화할 수 있는지 구해보세요.

for(int i=1;i<=n;i++)
	for(int j=v;j>=volume[i];j--)
		dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);

패키지 가득 차기 문제를 0으로 초기화하고 max를 플러스로 변경합니다
2. 완전 가방
N 개 아이템과 V 용량의 가방이 있으며, 각 아이템은 무한 개 사용 가능.i번째 아이템을 넣는 데 소모되는 공간은 Ci이고, 얻는 가치는 Wi다.구해: 어떤 물품을 가방에 넣으면 이 물품들이 소모하는 공간이 가방 용량을 초과하지 않고 가치가 가장 크다.

for(int i=1;i<=n;i++)
	for(int j=volume[i];j<=v;j++)
    	dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);

3. 다중 가방
바이너리 최적화

		int v=read(), n=read();
		int dp[M]={}; //dp[j]  j         ,       
		for(int i=1; i<=n; ++i)
		{
			int vol=read(), val=read(), num=read(); //  ,  ,  
			for(int k=1; k<num; num-=k,k<<=1)
				for(int j=v; j>=k*vol; --j)
					dp[j] = max(dp[j], dp[j-k*vol]+k*val);
			for(int j=v; j>=num*vol; --j)
				dp[j] = max(dp[j], dp[j-num*vol]+num*val);
		}

단조 최적화

		int v=read(), n=read();
		int dp[M]={};

		for(int i=1; i<=n; ++i)
		{
			int vol=read(), val=read(), num=read(); //  ,  ,  
			for(int k=0; k<vol; ++k) //       
			{
				int a[M], b[M], l=0, r=0; //  ,  ,   ,   ,     
				for(int j=k; j<=v; j+=vol)
				{
					int y = dp[j] - j/vol*val; //        

					while(l<r && y>=b[r-1]) r--; //  
					a[r] = j; b[r++] = y;

					while(a[l]<j-num*vol) ++l; //  

					dp[j] = b[l] + j/vol*val; //     
				}
			}
		}
		printf("%d
",dp[v] );

4. 세 가지 가방 혼합
모두 다중으로 풀 수 있고, 건수를 설정하면 된다.
5. 2차원 비용 가방
2차원 비용의 배낭 문제는 모든 물품에 대해 두 가지 다른 공간 소모를 가지므로 이 물품을 선택할 때 반드시 이 두 가지 대가를 동시에 지불해야 한다는 것을 말한다.모든 대가에 대해 지불할 수 있는 최대치(가방 용량)가 있다.물건을 어떻게 선택하면 가장 큰 가치를 얻을 수 있느냐고 물었다.이 두 가지 대가를 설정하면 각각 대가 1과 대가 2이고, i번째 물품에 필요한 두 가지 대가는 각각 Ci와 Di이다.두 가지 대가로 지불할 수 있는 최대치(두 가지 가방 용량)는 각각 V와 U이다.물품의 가치는 Wi이다.
새로 추가된 1차원은 일반적으로 건수이므로, 반복 순서를 정확하게 써야 한다.

    for(int i=1;i<=n;i++)
        for(int j=v;j>=volume[i];j--)
            for(int k=w;k>=weight[i];k--)
                dp[j][k]=max(dp[j][k],dp[j-volume[i]][k-weight[i]]+value[i]);

cty: 익숙한 동적 기획 제목에서 변형된 제목을 발견할 때 원래의 상태에서 1차원을 추가하여 새로운 제한을 만족시키는 것은 비교적 통용되는 방법이다.네가 본강에서 이런 방법을 초보적으로 체득할 수 있기를 바란다.
6.배낭 묶기
N 아이템과 V 용량의 가방이 있습니다.i번째 물품의 비용은 Ci이고, 가치는 Wi이다.이 물품들은 K조로 나뉘어 각 조의 물품이 서로 충돌하여 최대 하나를 선택한다.어떤 물품을 가방에 넣으면 이 물품의 비용 총계가 가방 용량을 초과하지 않고 가치 총계가 가장 클 수 있는지 구해 보세요.
반복 순서

for(int k=1;k<=p;k++) 
	for(int j=v;j>=0;j–) //              
		for(int i:part[k]) 
			dp[j]=max(dp[j],dp[j-volume[i]]+value[i]). 

8. 범용 물품
이런 물건을 고려하면 고정된 비용과 가치가 아니라, 그 가치는 당신이 분배한 비용에 따라 달라진다.이것이 바로 범용 물품의 개념이다.
범용 물품의 합: f v = m a x k = 0 v (h k + l v -3 k) fv = max_{k=0}^v(h_k + l_{v − k} ) fv​=maxk=0v​(hk​+lv−k​)
7. 의존하는 가방 문제
이런 가방 문제의 물품 사이에는 어떤 의존적인 관계가 존재한다.즉, 물품 i는 물품 j에 의존하고 물품 i를 선택하면 반드시 물품 j를 선택해야 한다는 뜻이다.간소화하기 위해서 우리는 먼저 어떤 물품도 다른 물품에 의존하고 다른 물품에 의존하지 않는다.또 여러 개의 물품에 동시에 의존하는 물품은 없다.
각 조 물품의 주부품 k를 확정한 후, 주부품 k의'부속품 집합'에 대해 먼저 01배낭을 1회 진행하고, 주부품 k의 물품 조 범용 물품을 구한다.조별 배낭을 이용하여 해답을 구하다.
9. 가방 질문 방법의 변화
출력 방안
구덩이를 남기다