1.题目
钱包里有一些硬币，1元，5元，10元，50元，100元，500元，现在用这些硬币去买自动贩卖机里价格为A的饮料。假设自动贩卖机所需金额必须是刚刚好，不能多不能少。问最少需要多少枚硬币
输入：
1元，5元，10元，50元，100元，500元每枚硬币的个数 和 A的值
输出：
凑成A的最少硬币数或者NOWAY
2.动规法解题
思路：先将当前的面额大的硬币尽量多用，当超过所规定的硬币数量时，去寻找之前硬币所能组成的组合。
子问题划分：二维备忘录dp[i][j] 代表前i种硬币凑成当前金额j所需的最少个数
辅助数组：curCoinNum[i][j]记录第i种硬币在金额为j时用了多少个
初值：
其中coinNum[i]是第i中硬币的个数
递推方程：
其中coins是6种硬币的面额
代码:
static int[] coins = {-1,1,5,10,50,100,500};
static int n = coins.length-1;
static int[] coinNum = new int[n+1];
static int A;
static int MAX = Integer.MAX_VALUE;
static String DP(){
//curCoinNum[i][j]代表 第i个硬币在价值为j的时候用了几个
int[][] curCoinNum = new int[n+1][A+1];
//动归求解，dp[i][j]表示前i个硬币对于价值j时所需的最小数量
int[][] dp = new int[n+1][A+1];
//初值
for(int i=1;i<=n;i++)
for(int j=1;j<=A;j++)
dp[i][j] = MAX;
//初值 ,当前价值只用第一种硬币组成
for(int j=1;j<=A;j++)
if(j <= coinNum[1])
dp[1][j] = j;
for(int i=2;i<=n;i++){
for(int j=1;j<=A;j++){
if(coinNum[i]>0 && j>=coins[i]){
//尽量先将当前硬币用光
if(curCoinNum[i][j-coins[i]]+1 <= coinNum[i]){
//若上一个硬币也无法达到j-coins[i]的价值，则当前硬币也无法达到
dp[i][j] = dp[i][j-coins[i]]==MAX?MAX:dp[i][j-coins[i]]+1;
curCoinNum[i][j] = curCoinNum[i][j-coins[i]] + 1;
}else{
//当前硬币已用尽时
int min = dp[i-1][j];
for(int k=1;k<i;k++){
if(dp[k][j-coins[i]]<MAX && min>(dp[k][j-coins[i]]+1)){
min = dp[k][j-coins[i]]+1;
}
}
if(min < Integer.MAX_VALUE)
curCoinNum[i][j] = 1; //若可凑成当前金额，则代表只用了一个当前硬币
dp[i][j] = min;
}
}else
dp[i][j] = dp[i-1][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=A;j++){
System.out.print(curCoinNum[i][j] + " ");
}
System.out.println();
}
if(dp[n][A] == MAX)
return "NOWAY";
return dp[n][A]+"";
}
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
for(int i=1;i<=6;i++){
coinNum[i] = Integer.parseInt(input[i-1]);
}
A = Integer.parseInt(input[6]);
System.out.println( DP());
}
3. 回溯法解题
思路：此题可转化成为0-1背包问题（将每种硬币乘以其数量），这样一来我们只用考虑取值是1的硬币的个数
输入：n个硬币（面值可相同）
解空间：n+1层高的满二叉树（左1右0）
可行解：A为总金额
最优解：众多可行解中取值为1的硬币最少的解
代码：
static int[] coin = {1,5,10,50,100,500};
static List<Integer> coins;
static int A, //初始给定金额
n, //总硬币数
x[], //记录当前硬币的0，1取值
bestx[],//记录最优解的0，1取值
cv, //当前目标金额
bestn, //最少硬币个数
cn; //当前硬币个数
static void Backtrack(int i){
if(i>=n){
if(cv==0){
if(bestn > cn){
for(int j=0;j<n;j++)
bestx[j] = x[j];
bestn = cn;
}
}
return;
}
if(cv >= coins.get(i)){
x[i] = 1;
cv -= coins.get(i);
cn += 1;
Backtrack(i+1);
cn -= 1;
cv += coins.get(i);
}
Backtrack(i+1);
}
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
A = Integer.parseInt(str[str.length-1]);
cv = A;
coins = new ArrayList<Integer>(); //将所有硬币化为单个对象，放入集合之中
bestn = Integer.MAX_VALUE;
for(int i=str.length-2;i>=0;i--){
int num = Integer.parseInt(str[i]);
for(int j=0;j<num;j++){
coins.add(coin[i]);
}
}
n = coins.size();
x = new int[n];
bestx = new int[n];
// for(int i=0;i<coins.size();i++)
// System.out.print(coins.get(i)+" ");
Backtrack(0);
System.out.println(bestn==Integer.MAX_VALUE?"NOWAY":bestn);
for(int i=0;i<n;i++){
if(bestx[i] != 0)
System.out.println(coins.get(i));
}
}
