C言語-多重リュック問題

多重リュックサック問題
質問:N種類の品物とV容量のリュックサックがあります.第i種の物品は最大n[i]件が利用可能であり、1件当たりの費用はc[i]、価値はw[i]である.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
分析:
この問題は完全なリュックサックの問題と似ている.基本的な方程式は、完全なリュックサック問題の方程式を少し変えるだけでよい.i番目の物品にはn[i]+1の戦略があるからだ.0件、1件......n[i]件を取る.f[i][v]に、前のi種の物品がv容量のリュックサックの最大重み値を適切に入れることを示すと、状態遷移方程式がある.f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
複雑度はO(V*Σn[i]).
別の方法:
もう一つの書きやすい基本的な方法は01リュックに変換することです.Σn[i]の01リュック問題は,直接解き,複雑度は依然としてO(V*Σn[i]).
しかし、01リュックの問題に変換した後、完全なリュックのように複雑さを低減することを期待しています.依然としてバイナリの思想を考えて、私达は第i种类の物品をいくつかの物品に交换することを考えて、原问题の中で第i种类の物品が取ることができるすべての策略--0を取ります..n[i]件--いずれもいくつかの交換後の品物を取ることに等価である.また、n[i]件を超えるポリシーは必ず現れない.
方法は、i番目の物品をいくつかの物品に分け、その中で各物品には係数があり、この物品の費用と価値はいずれも元の費用と価値にこの係数を乗じている.これらの係数をそれぞれ1,2,4,...,2^(k−1)、n[i]−2^k+1であり、kはn[i]−2^k+1>0を満たす最大整数である.例えば、n[i]が13の場合、このような物品は、係数がそれぞれ1,2,4,6の4つの物品に分割される.
分割されたこれらのアイテムの係数和はn[i]であり,n[i]アイテムより多くのi番目のアイテムを取ることは不可能であることを示している.また、この方法は0に対しても保証できる.n[i]間の各整数は、いくつかの係数の和で表すことができ、この証明は0に分けることができる.2^k-1と2^k..n[i]2つのセグメントでそれぞれ議論したが、難しくないので、自分で考えてみてほしい.
このようにi番目のアイテムをO(log n[i])アイテムに分類し,原問題を複雑度$O(V*に変換する.\Sigma log\; n[i])の01バックの問題は、大きな改善です.$
次に、O(log amount)時間が多重リュックサック中の物品を処理する過程を示し、amountは物品の数を表す.

procedure MultiplePack(cost,weight,amount)

    if cost*amount>=V

        CompletePack(cost,weight)

        return

    integer k=1

    while k<amount

        ZeroOnePack(k*cost,k*weight)

        amount=amount-k

        k=k*2

    ZeroOnePack(amount*cost,amount*weight)


    ：

 1 /******************      *********************/

 2 #include <iostream>

 3 #include <vector>

 4 #include <math.h>

 5 using namespace std;

 6 #define EMPTY

 7 #define INF -65536

 8 const int V=1000;//    

 9 const int T=5;//      

10 int f[V+1];

11 int c[T]={40,100,30,80,400};

12 int w[T]={3,8,1,3,5};

13 int n[T]={10,5,9,13,7};

14 vector <int> n_list;//           

15 vector <int> c_list;//                 

16 vector <int> w_list;//                 

17 void initpackage()//       

18 {

19     int x=0;

20     for(int i=0;i<T;i++)

21     {

22         int p=1;

23         cout<<n[i]<<":";

24         while((n[i]-pow(2,p)+1)>=0)

25         {

26             cout<<pow(2,p-1)<<" ";

27             n_list.push_back(pow(2,p-1));

28             c_list.push_back(c[i]*pow(2,p-1));

29             w_list.push_back(w[i]*pow(2,p-1));

30             p++;

31         }

32         x=n[i]-pow(2,p-1)+1;

33         if(x>0)

34         {

35             cout<<x<<" ";

36             n_list.push_back(x);

37             c_list.push_back(c[i]*x);

38             w_list.push_back(w[i]*x);

39         }

40         cout<<endl;

41     }

42 }

43 int package()

44 {

45     initpackage();

46     int size;

47     size=n_list.size();

48     #ifdef EMPTY

49     for(int i=0;i<=V;i++)

50     {

51         f[i]=0;

52     }

53     #else

54     f[0]=0;

55     for(int i=1;i<=V;i++)

56     {

57         f[i]=INF;

58     }

59     #endif // EMPTY

60     for(int i=0;i<size;i++)

61     {

62         for(int v=V;v>=c_list[i];v--)

63         {

64             f[v]=max(f[v],f[v-c_list[i]]+w_list[i]);

65         }

66     }

67     return f[V];

68 }

69 int main()

70 {

71     int temp;

72     cout<<"c[i]    ：";

73     for(int i=0;i<T;i++)

74     {

75         cout<<c[i]<<" ";

76     }

77     cout<<endl;

78     cout<<"w[i]    ：";

79     for(int i=0;i<T;i++)

80     {

81         cout<<w[i]<<" ";

82     }

83     cout<<endl;

84     cout<<"n[i]    ：";

85     for(int i=0;i<T;i++)

86     {

87         cout<<n[i]<<" ";

88     }

89     cout<<endl;

90     temp=package();

91     cout<<temp<<endl;

92     return 0;

93 }