最少硬币问题(多重背包问题)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

最少硬币问题

问题描述:设有n种不同面值的硬币,各硬币的面值存在于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0£m£20001,设计一个最少硬币找钱m的方法。

算法设计:对于给定的1£n£10 ,硬币面值数组T和可以使用的各种面值的硬币数组Coins,以及钱数m, 0£m£20001,计算找钱m的最少硬币数。

数据输入:由文件input.Txt提供输入数据,文件的第1行中只有一个整数给出n的值,第2行起每行两个数,分别是T[j]和Coins[j]。最后一行是要找的钱数m。

结果输出:将计算出的最少硬币数输出到文件output.txt。问题无解时输出-1。

这个题目,用一个二维的动态转移方程比一维动态转移方程更容易理解。

下面的解法,是基于一维动态转移方程。

/******************************************************************** ** @file    test.cpp ** @author  liuke ** @date    Fri Apr 22 23:50:50 2011 ** @brief    **************************动态规划实现********************************  长度为m的数组f[1...m]中存放一系列子结果,即f[i]为要凑的钱数为i时  所需的最少硬币数,则c[m]为所求;  当要找的钱数i(1<i<m)与当前所试探的硬币面值k相等时,结果为1,即c[i]=1  当i大于当前所试探硬币面值k时,若f[i]为0,即还未赋过值,且c[i-k]不为0,  即从i元钱中刨去k元后剩下的钱数可以找开, 则c[i]=c[i-k]+1  若f[i]不为0,即已赋过值,则f[i]为f[i-k]+1和f[i]中较小的 ** 
//硬币问题就是一个多重背包问题//动态迁移方程为 dp[k] = min{dp[k-t[i]]+1,dp[k]}//就是,将第i个硬币拿出去得到的一个最少的找硬币数+1,和原硬币数相比最小的那个就是结果//另外一种思路,可以将所有的硬币价值都放在一个数组,就变成了0-1背包问题,所需考虑的就是放不放的问题 #include<iostream>using namespace std;int min(int a,int b);int main(){   int n; //n种不同面值的硬币   int m;   int i , j ,k;   cout<<"请输入有几种不同的面值:";   cin>>n;   int *t =new int[n+1];               //硬币的面值存放在t数组中 -- 价值   int *coin = new int [n+1];      //可以使用的硬币个数存放在coin中--个数   cout<<"请输入"<<n<<"组硬币的面值和对应的个数(中间用空格隔开):"<<endl;   for(i = 1 ;i<n+1;i++)       cin>>t[i]>>coin[i];   cout<<"请输入要找的钱数m:";   cin>>m;   int dp[20002]={0} ;   //dp[i] 用来记录钱数为i时的最少的硬币数   for(i=1;i<=m;i++)       dp[i] = 99999;   //dp[0] = 0;   for(i = 1 ;i <= n ; i++)    //硬币面值的种数       for(j = 1 ; j <= coin[i] ; j++)   //硬币的面值的个数           for( k = m ; k >= t[i] ;  k-- )               {               dp[k] = min(dp[k-t[i]] +1,dp[k]);               //cout<<k<<": "<<dp[k]<<endl;  用于测试使用           }   cout<<"最少需要用到的硬币个数是:";   if(dp[m] == 99999)cout<<-1<<endl;   else cout<<dp[m]<<"个"<<endl;} int min(int a,int b){   return a<b?a:b;}

点这里可以跳转到人工智能网站