在原有的货币基础上扩充，比如1，2，3，那我认为有无限的-1，-2，-3（因为商人有无数的货币而且相对于我们是负的），这样这个问题又变成了普通的货币问题，但是也带来了一些问题，而解决这些问题花了一些额外的开销，一个没有想清楚的问题是开多大的数组，因为引入了负的可能，所以数组不可能计算到total就为止，由于很晚了，只想到这里，
#include <iostream>
#include <vector>
/*
    pkoj fewest coin
*/
using namespace std;
struct dp_res
{
    int res;
    vector<int> cost;
};
int coins_dp(int coins[],int nums[],int length,int total)
{
    int max=coins[0];
    for(int i=1;i<length;i++)
    {
        if(max<coins[i])
            max=coins[i];
    }
    int size=20000;
    dp_res* res=new dp_res[size+1];
    for(int i=0;i<=size;i++)
    {
        res[i].res=1111;
    }
    res[0].res=0;
    for(int i=0;i<length;i++)
    {
        if(coins[i]>0)
        {
            res[coins[i]].res=1;
            res[coins[i]].cost.push_back(coins[i]);
        }
    }
    for(int j=1;j<=size;j++)
    {
        for(int i=0;i<length;i++)
        {
            if(j>=coins[i]&&(j-coins[i])<=size&&res[j].res>(res[j-coins[i]].res+1))
            {
                int count=1;
                for(int k=0;k<res[j-coins[i]].cost.size();k++)
                {
                    if(res[j-coins[i]].cost.at(k)==coins[i])
                        count++;
                }
                if(nums[i]>=count)
                {
                    res[j].res=res[j-coins[i]].res+1;
                    res[j].cost=res[j-coins[i]].cost;
                    res[j].cost.push_back(coins[i]);
                }
            }
        }
    }
    for(int j=size;j>=1;j--)
    {
        for(int i=0;i<length;i++)
        {
            if(j>=coins[i]&&(j-coins[i])<=size&&res[j].res>(res[j-coins[i]].res+1))
            {
                int count=1;
                for(int k=0;k<res[j-coins[i]].cost.size();k++)
                {
                    if(res[j-coins[i]].cost.at(k)==coins[i])
                        count++;
                }
                if(nums[i]>=count)
                {
                    res[j].res=res[j-coins[i]].res+1;
                    res[j].cost=res[j-coins[i]].cost;
                    res[j].cost.push_back(coins[i]);
                }
            }
        }
    }
    if(res[total].res==1111) cout<<-1<<endl;
    else cout<<res[total].res<<endl;
    return 0;
}
int main()
{
    int N,T;
    cin>>N>>T;
    int* coins=new int[2*N];
    int* nums=new int[2*N];
    for(int i=0;i<2*N;i+=2)
    {
        cin>>coins[i];
        coins[i+1]=-coins[i];
    }
    for(int i=0;i<2*N;i+=2)
    {
        cin>>nums[i];
        nums[i+1]=1000000;
    }
    coins_dp(coins,nums,2*N,T);
    return 0;
}
希望有人提出意见，前后过了2遍，我自己都觉得sb了