HDU 3591 多重背包

HDU 3591 多重背包

給出N種錢幣和M

給出N種錢幣的面值和個數

NPC拿著這N些錢幣去買價值M的物品，可以多付，然後被找零，找零的錢也為這些面值，但沒有數量限制

問最少經手的錢幣數量

對於NPC做一個付款多重背包

然後對於找零做一個完全背包

ans=Min(dp1[i]+dp2[i-m],ans);

#include "stdio.h"
#include "string.h"


int n,m;
int dp1[20010],dp2[20010],c[20010],v[20010];
void onezero_pack(int v,int k)
{
    int i;
    for (i=20000;i>=v;i--)
        if (dp1[i-v]!=-1 && (dp1[i-v]+k=20000)
        complete_pack(v);
    else
    {
        k=1;
        while (k0) onezero_pack(c*v,k);
    }
}

int Min(int a,int b)
{
    if (a