POJ 3260 The Fewest Coins(ダイナミックプランニング+マルチバックパック+フルバックパック)

タイトル接続:クリックしてリンクを開く
ジョンはN种类の货币があって、それぞれの货币は相応の価値Vと数量Cがあって、彼はただの货币でTの货物を买って、闻きます:払った硬貨の数と取り戻した硬貨の数は少なくとも何个ですか?
解題構想:Johnの貨幣は有限で、だから多重リュックサックでTの貨物を買うのに最も使う貨幣の数を解くことができて、売り手の貨幣の数は無限で、だから完全なリュックサックで売り手のお金を探す最も少ない数を計算することができます;最後に2つの配列で取引に関与する最も少ない通貨数を遍歴すればよい.考えはそうですが、大きなポイントは、2つのリュックサックのリュックサックの上限をどのように確定するかということです.最初はジョンが獲得した最大額面の貨幣総額をリュックサックの上限としたが、Runtimeは鳩かごの原理を理解し、具体的には以下の通りである.
Johnの支払数は最大maxv*maxv+m
証明は次のとおりです.
Johnの支払数がmaxv*maxv+mより大きい場合、即払硬貨の数がmaxvより大きい場合、ハトかごの原理によれば、少なくとも2つのものとmaxvの型取りの値が等しい(この意味は、少なくともmaxv+1個の硬貨がmaxvに余剰を求め、その後、余剰数が[0,maxv-1]の範囲に属し、少なくとも2つの硬貨の余剰数が同じであるに違いない).このコインは、より少ないmaxvで代用することができます.(通俗的にはもっと少ない大金でたくさんの小銭に両替できるので、金貨の数が少なくなります).
そこでリュックサックの配列を20000まで開いて...成功した!具体的なコードは以下の通りで、コメントは詳細です.
コードは以下の通りです:(注釈のコードがあり、私が前に述べたRTを招いた場所です)

#include
#include
#include
#define INF 999999999
using namespace std;
int dp1[20005],dp2[20005];
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        int val[150],num[150];
       // int maxnv=0;
        for(int i=1; i<=n; i++)
        {
            cin>>val[i];
            //if(maxnv
             //  maxnv=val[i];

       }
       // int W=maxnv*maxnv+m;
        for(int i=1; i<=n; i++)
            cin>>num[i];
        for(int i=1; i<=20000; i++)
            dp1[i]=dp2[i]=INF;
        dp1[0]=dp2[0]=0;
        int i,j,k;
        for(i=1; i<=n; i++)     //        01           
        {
            for(k=1; k<=num[i]; k*=2)
            {
                for(j=20000; j>=k*val[i]; j--)
                {
                    dp1[j]=min(dp1[j],dp1[j-k*val[i]]+k);
                }
                num[i]-=k;
            }

            for(j=20000; j>=num[i]*val[i]; j--)
            {
                dp1[j]=min(dp1[j],dp1[j-num[i]*val[i]]+num[i]);
            }
        }
        for(int i=1; i<=n; i++)     //                
        {
            for(int j=val[i]; j<=20000; j++)
                dp2[j]=min(dp2[j],dp2[j-val[i]]+1);
        }
        int ans=INF;
        for(int i=m; i<=20000; i++)
        {
            ans=min(ans,dp1[i]+dp2[i-m]);
        }
        if(ans==INF)
            cout<

~step by step