リュックサック9の4(3種類のリュックサックを混ぜた問題)

 1 /*

 2  01  ，    ，             ，            

 3          ，      

 4                 

 5 for(int i=1; i<=N; ++i)

 6 if( i    01  )

 7     zeroOnePack(c[i],w[i]);

 8 else if( i        )

 9     completePack(c[i],w[i]);

10 else if( i          )

11     multiplePack(c[i],w[i],n[i]);

12 

13             ，              ，

14            ，                  

15                  

16 */

17 

18 #include <stdio.h>

19 #include <string.h>

20 int cash;

21 int n[11],dk[11];

22 int dp[1000000];

23 inline int max(const int &a, const int &b)

24 {

25     return a < b ? b : a;

26 }

27 void CompletePack(int cost)

28 {

29     for(int i=cost; i<=cash; ++i)

30         dp[i] = max(dp[i],dp[i-cost]+cost);

31 }

32 void ZeroOnePack(int cost)

33 {

34     for(int i=cash; i>=cost; --i)

35         dp[i] = max(dp[i],dp[i-cost]+cost);

36 }

37 void MultiplePack(int cnt, int cost)

38 {

39     if(cnt*cost >=cash)//   i              ，          

40         CompletePack(cost);

41     else

42     {

43         int k = 1;//     

44         while(k<cnt)//              k

45         {

46             ZeroOnePack(cost*k);

47             cnt -=k;

48             k<<=1;

49         }

50         ZeroOnePack(cnt*cost);

51     }

52 }

53 int main()

54 {

55     //            

56     return 0;

57 }