HDU 2159 FATE (동적 계획 dp 의 2 차원 완전 가방 문제)

주소
사고: 동적 계획 dp 의 2 차원 완전 가방 문제
상태 방정식 이 관건 이 야...
/*dp[j][l] = Max(dp[j][l],dp[j-1][l-b[i]]+a[i]) l 포인트 의 인내 도 를 떨 어 뜨리 고 j 개 몬스터 를 처치 한 후 획득 한 최대 경험 치 를 나 타 냅 니 다. * /  
제목 분석:
2 차원 비용 의 가방 문 제 는 모든 물품 에 대해 두 가지 서로 다른 비용 을 가 진 다 는 것 을 말한다.이 물건 을 선택 하려 면 반드시 이 두 가지 대 가 를 동시에 지불해 야 한다.모든 대 가 는 지불 할 수 있 는 최대 치 (가방 용량) 가 있다.아 이 템 을 선택 하면 가장 큰 가 치 를 얻 을 수 있 는 방법 을 묻는다.이 두 가지 대 가 를 각각 대가 1 과 대가 2 로 설정 하고 i 번 째 물품 에 필요 한 두 가지 대 가 는 각각 a [i] 와 b [i] 이다.두 가지 대가 로 지불 할 수 있 는 최대 치 (두 가지 가방 용량) 는 각각 V 와 U 다.물품 의 가 치 는 w [i] 이다.
비용 은 1 차원 을 더 하고 상태 도 1 차원 만 더 하면 된다.f [v] [u] 를 설정 하면 앞의 i 개 물품 이 각각 v 와 u 를 지불 할 때 얻 을 수 있 는 최대 가 치 를 나타 낸다.상태 전이 방정식 은:
f[v][u]=max{f[i-1][v][u],f[v-a[i]][u-b[i]]+w[i]}
앞에서 말 한 방법 과 같이 2 차원 배열 만 사용 할 수 있 습 니 다. 모든 아 이 템 이 한 번 만 찾 을 수 있 을 때 변수 v 와 u 는 역순 으로 순환 하고 아 이 템 이 가방 문제 와 같 을 때 순서 적 인 순환 을 사용 합 니 다.물품 이 여러 개의 가방 문제 가 있 을 때 물품 을 나 누 어 줍 니 다.
여기까지 오 면 생각 이 별로 없 을 것 같 습 니 다. 코드 를 보면 2 차원 비용 가방 을 잘 이해 할 수 있 을 것 같 습 니 다.
우선 완전 가방 의 템 플 릿 을 살 펴 보 겠 습 니 다.
void CompletePack(int value,int weight){ int i; for(i=weight;i<=V;i++)  dp[i]=max(dp[i],dp[i-weight]+value);   }
코드 는 다음 과 같 습 니 다:

 1 #include<stdio.h>

 2 #include<string.h>

 3 #define N 110

 4 int dp[N][N];//    

 5 int a[N],b[N];

 6 int max(int x,int y)

 7 {

 8     return x>y?x:y;

 9 }

10 int main()

11 {

12     int n,m,k,s,i,j,l;

13     while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)  //n   ，m    ，k     ，s      

14     {

15         for(i=0;i<k;i++)

16         scanf("%d%d",&a[i],&b[i]);  //              

17         memset(dp,0,sizeof(dp));

18         for(i=0;i<k;i++)  //      

19         { 

20             for(j=1;j<=s;j++)  //    ，      s

21             {

22                 for(l=b[i];l<=m;l++)  //          for  

23                   dp[j][l]=max(dp[j][l],dp[j-1][l-b[i]]+a[i]); //dp[j][l]       l     ，    j   ，         

24             }

25         }

26         for(i=0;i<=m;i++)   //i    0   m   dp[j][l]       l     ，    j   ，         

27           if(dp[s][i]>=n) break;  //    m     ，    s    ,         

28         if(dp[s][i]<n)   //break               。。。 

29           printf("-1
");  //      s                            -1  

30         else

31           printf("%d
",m-i);  ////   s    ，   i      ，            m-i

32     }

33     return 0;

34 } 

35