【题目记录】——POJ 3260 The Fewest Coins 混合背包

末蓝、 2022-09-02 05:16 122阅读 0赞

# POJ 3260 The Fewest Coins #

题目地址【[POJ 3260 The Fewest Coins][]】  
题意：John要去买价值为m的商品. 现在的货币系统有n种货币,对应面值为val\[1\],val\[2\]…val\[n\]. 然后他身上每种货币有num\[i\]个. John必须付给售货员>=m的金钱, 然后售货员会用最少的货币数量找钱给John.

问你John的交易过程中, 他给售货员的货币数目+售货员找钱给他的货币数目 的和最小值是多少?  
思路：  
将付钱和找钱看做两各部分分别是多重背包问题和完全背包问题，找到在大于等于物品价格的价钱下最少的付钱硬币数和找钱硬币数加到一起的最小值即可。  
AC代码：

/* ** Author:skj ** Time:7-30 ** function:混合背包 最少的硬币 http://poj.org/problem?id=3260 */
    #include <iostream>
    #include <cstring>
    #define INF 0x3f3f3f3f
    using namespace std;
    
    const int pay = 10000+120*120+5;
    const int change = 120*120+5;
    const int maxm = 120 +1;
    int dp_pay[pay];
    int dp_change[change];
    int v[maxm];
    int c[maxm];
    int num[pay];
    void multi_knapsack(int n,int m)
    { 
        dp_pay[0] = 0;
        for(int i = 1; i <= n; i++)
        { 
            memset(num,0,sizeof(num));
            for (int j = v[i]; j <= m; j++)
            { 
                if(j >= v[i]&&num[j-v[i]] < c[i])
                { 
                    dp_pay[j] = min(dp_pay[j],dp_pay[j - v[i]] + 1);
                    num[j] = num[j - v[i]] + 1;
                }
            }
        }
    }
    void complete_knapsack(int n, int m)
    { 
        dp_change[0] = 0;
        for(int i = 1; i <= n; i++)
        { 
            for(int j = v[i]; j <= m; j++)
            { 
                dp_change[j]=min(dp_change[j],dp_change[j-v[i]] + 1);
            }
        }
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        cin.sync_with_stdio(0);
        cin.tie(0);
        memset(dp_pay,INF,sizeof(dp_pay));
        memset(dp_change,INF,sizeof(dp_change));
        int n, m;
        cin >> n >> m;
        int maxv = 0;
        for(int i = 1; i <= n; i++)
        { 
            cin >> v[i];
            maxv = max(maxv,v[i]);
        }
        maxv *= maxv;
        for(int i = 1; i <= n; i++)
        { 
            cin >> c[i];
        }
        multi_knapsack(n,m + maxv);
        complete_knapsack(n,maxv);
        int ans = INF;
        for(int i = 0; i <= 120*120; i++)
        { 
            ans = min(ans,dp_pay[i+m]+dp_change[i]);
        }
        if(ans == INF)
        { 
            cout << -1 << endl;
        }
        else
        { 
            cout << ans << endl;
        }
        return 0;
    }

[POJ 3260 The Fewest Coins]: http://poj.org/problem?id=3260