子问题定义: 定义一个二维数组b,其中b[i][j]表示前i个币种是否能兑换价格j，表示第i个币种的面值，第i个币种的使用有两种情况，若使用，则b[i][j]=b[i-1][j-]，若不使用，则b[i][j]=b[i-1][j]
递归关系:
初值设定：
求解顺序：
按下标从小到大依次求解数组b每一行的值，最后二维数组b的右下角元素值即为最终的解。
package org.xiu68.ch06.ex7;
public class Ex6_18 {
//面值为x1,x2,x3,...,xn的硬币是否能兑换价格v,每个硬币只能使用一次(解法有点类似于0-1背包问题)
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] x=new int[]{1,3,5,6};
for(int i=0;i<=20;i++)
convertChange(x, i);
}
//coin:硬币面值
//v:要兑换的价格
public static void convertChange(int[] x,int v){
boolean[][] b=new boolean[x.length+1][v+1]; //b[i][j]表示使用前i个币种是否能兑换价格j
for(int i=0;i<=x.length;i++)
b[i][0]=true; //表示任何币种可以兑换价格0
for(int j=1;j<=v;j++)
b[0][j]=false; //没有硬币则不可以兑换任何大于0的价格
for(int i=1;i<=x.length;i++){
for(int j=1;j<=v;j++){
boolean use=false;
if(j>=x[i-1]) //价格j要大于等于第i个币种才能用第i个币种兑换
use=b[i-1][j-x[i-1]]; //使用第i个币种的情况 ,x[i-1]:第i个币种下标为i-1
boolean nuse=b[i-1][j]; //不使用第i个硬币的情况
if(use || nuse) //只要有一种情况可以兑换则前i个币种能兑换价格j
b[i][j]=true;
else
b[i][j]=false;
}//for2
}//for1
System.out.print(v+":"+b[x.length][v]);
if(b[x.length][v]){
System.out.print(" use: ");
for(int i=x.length,j=v;i>0 && j>0;){
if(j>=x[i-1] && b[i-1][j-x[i-1]]){ //使用了第i个币种
System.out.print(x[i-1]+" ");
j=j-x[i-1];
i--;
}else{ //没有使用第i个币种
i--;
}
}//for
}
System.out.println();
}
//运行结果：
/*0:true use:
1:true use: 1
2:false
3:true use: 3
4:true use: 3 1
5:true use: 5
6:true use: 6
7:true use: 6 1
8:true use: 5 3
9:true use: 6 3
10:true use: 6 3 1
11:true use: 6 5
12:true use: 6 5 1
13:false
14:true use: 6 5 3
15:true use: 6 5 3 1
16:false
17:false
18:false
19:false
20:false*/
}