01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)

dp동적 기획은 정말 까다롭다. 가장 간단한 가방 문제만 가지고 애를 쓴다.
생각!생각!생각!점차적으로 관계를 찾는 것과 유사하다. 
가방 문제, 두 가지 상태로 할까요, 말까요?사실 배낭을 놓을지 안 놓을지에 관한 문제를 이진법으로 표현한다면
잘 이해합니다. 0은 놓지 않는 것이고 1은 놓지 않는 것입니다.그러면 기존의 상황에 대해 n개의 물품이 있다고 가정하면 2진법에 대응하는 길이는 n으로 각 물품에 대해 01로 000xx~~111xx수의 크기를 몇 자리pow(2,n)로 표시해야 한다.

for(i=0;i

01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v] = 맥스 {f[i-3-1] [v], f[i-3] [v-wei[i]] +val [i]}로 전환하는 것이다.앞에는 안 넣고, 뒤에는 넣고, 넣으면 가방의 용량이 줄어든 후의 + 넣는 가치 = 이때 넣는 총 가치, 양자 비교!1차원 방정식 역순 역순으로 전환하는 목적은 다음 f[v]와 f[v-we[i]]+val[i]가 이전 상태임을 확보하는 것이다.

for(i=0;i=we[i];j--) //  !
	{
		dp[j]=max(dp[j],dp[j-we[i]]+val[i]);
	}

가방 제목 HDU2546: 밥카드http://acm.hdu.edu.cn/showproblem.php?pid=2546   HDU1171:BigEvent in HDU http://acm.hdu.edu.cn/showproblem.php?pid=1171HDU2602: BoneCollector(템플릿 문제)http://acm.hdu.edu.cn/showproblem.php?pid=2602HDU2639: BoneCollector II(01 가방 제 k 우대)http://acm.hdu.edu.cn/showproblem.php?pid=2639   HDU2955:Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955   HDU3466:ProudMerchants http://acm.hdu.edu.cn/showproblem.php?pid=3466HDU1864: 최대 청구 금액http://acm.hdu.edu.cn/showproblem.php?pid=1864
완전 배낭 문제. 01배낭에서 물품 개수를 무한개로 바꾸면 2진법 사상은 개수를 사용하는 데 좋지 않다. 왜냐하면 당신은 무수한 개를 사용할 수 있기 때문이다. 이때 무제한일 때 01을 바탕으로 최적화할 수 있지만 가치가 작고 무게가 큰 것을 최적화시킬 수 있다. 이런 것은 선택하지 않을 것이다.그러나 극단적인 문제는 해결하기 어렵다.같은 완전 가방의 전환 f[i][v]=Max{f[i-1][v-k*c[i]+k*w[i]|0<=k*c[i]<=v}k의 수치가 다른 f[][]의 권한도 변경됩니다. k는 1,2,3,4,5,6 무수한 개를 갈 수 있습니다.

for i=1->>n;
    for j=0-->>V//          
        f[v]=max{f[v],f[v-c[i]]+w[i]}

순서는 우리가 하나하나에 대해 몇 가지 가능성을 가지고/*를 사용할 수 있다는 것을 보장한다. 이것은 바로 모든 물품을 한 번만 선택할 수 있도록 하기 위해서이다.'제i물품을 선택한다'는 전략을 고려할 때 근거는 이미 제i물품을 선택한 하위 결과가 없다는 것이다. f[i-1][v-c[i]]].현재 완전 가방의 특징은 바로 모든 아이템이 무한 아이템을 선택할 수 있다는 것이다. 그래서'제i종 아이템 추가'라는 전략을 고려할 때 이미 제i종 아이템을 선택한 하위 결과 f[i][v-c[i]]가 필요하기 때문에 v=0...V의 순서 순환.이것이 바로 이 간단한 절차가 왜 성립되었는가의 이치이다.*/-->황소의 완전 가방 제목: Hdu 1114:http://acm.hdu.edu.cn/showproblem.php?pid=1114  Hdu 1248: http://acm.hdu.edu.cn/showproblem.php?pid=1248 Hdu2159: http://acm.hdu.edu.cn/showproblem.php?pid=2159
다중 가방: 모함수와 유사하지만 모함수는 사실 더 잘 이해한다.N가지 아이템과 V 용량의 백팩이 있습니다.제i종 물품은 최대 n[i]건이 사용 가능하며, 건당 비용은 c[i]이며, 가치는 w[i]이다.어떤 물품을 가방에 넣으면 이 물품의 비용을 가방 용량을 초과하지 않고 가치 총화의 최대 모함수에 대한 사상도 당신에게 가치를 줄 수 있습니다. 물품 수량의 제한을 모은 다음에 f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}< 각 n[i]의 모든 물품을 하나의 독립된 물품으로 간주하고이 n[i]개 아이템이 표시할 수 있는 무게는 실용log n[i]개를 조합한 아이템으로 표시할 수 있다.다중 가방 Hdu2191:http://acm.hdu.edu.cn/showproblem.php?pid=2191 Hdu 2844: http://acm.hdu.edu.cn/showproblem.php?pid=2844 Poj 1014 http://poj.org/problem?id=1014