dfs加动态规划

解题思路:

注意事项:

参考代码:

import java.util.Scanner;
public class Main {
private static int[] a;
private static int n;
private static int k;
private static int max=0;
private static int[] b=new int[100];
public static void main(String[] args) {
   Scanner input=new Scanner(System.in);
   n=input.nextInt();
   k=input.nextInt();
  a=new int[40]; //存可能的面值
  a[0]=1;  //必须有面值1
  dfs(1);  //开始搜索，从第二个面值开始枚举
  for (int i = 0; i <k; i++) {
System.out.print(b[i]+" ");
}
  System.out.println("\nMAX="+max);
}
private static void dfs(int i) {
if(i==k){//举例完k种
chexk();
}else{
for(int j=a[i-1]+1;j<=a[i-1]*n+1;j++){//下一个面值一定在上一个面值+1到上一个面值*最多贴的张数+1之间
a[i]=j;
dfs(i+1);
}
}
}
private static void chexk() {//动态规划求最大值
int dp[]=new int[1000];//最大连续尽量大一点，避免越界。下标i表示当前邮资，dp[i]表示所需最少张数
dp[0]=0;//邮资为零时一定是零张
int i=0;
while(dp[i]<=n){//当最少张数大于最多可贴张数时跳出
i++;
dp[i]=99999;//假设当前邮资下需要贴99999张邮票
for(int j=0;j<k&&a[j]<=i;j++){//寻找所有的邮票，且这张邮票的面值不大于当前的邮资
if(dp[i-a[j]]+1<dp[i])//当前邮资减去这张邮票面值张数加一如果小于当前邮资现用组合张数，则替换
dp[i]=dp[i-a[j]]+1;
}
}
if(i-1>max){
max=i-1;
for (int j = 0; j <k; j++) {
b[j]=a[j];
}
}
}
}