凑硬币
本文最后更新于 202 天前,其中的信息可能已经有所发展或是发生改变。

(6)凑硬币

这个题目算是我对动态规划进一步提升的桥梁

/*(有问题)
 换金币:
  目前有9元,5元,2元三种面值的金币若干个,现在要找回21元的硬币
  则用什么样的组合使得兑换金币数最少;
     分析:
         1.转化为子问题;
         就是把一个大问题分成若干个子问题,对问题进行降价,通过降价将问题简化
         从而实现问题求解(把所有需要硬币数减去最后一个硬币,就得到k-1个硬币的子问题)
         2.转移方程:
         起初先列出最开始的子问题,找规律
          f(x)=min{f(x-2)+1,f(x-5)+1,f(x-9)+1}
          要想求出最少组合方法,则求出x-9,x-5,x-2中的最小值再加上一就是问题的求解
         3.按照实际逻辑设置边界情况和初始条件
         初始条件 f(0)=0;表示0元需要0个硬币
         边界条件 x-2,x-5,x-9小于零时,默认这种情况是拼不出来的
         即利用最大值max表示
         4.确定计算顺序进行求解
   */
  Scanner scan=new Scanner(System.in);
  int n=scan.nextInt();
  int number[]=new int [n];
  int sum=scan.nextInt();
  for (int i = 0; i < n; i++) {
     number[i]=scan.nextInt();
  }
  int dp[]=new int [sum+1];
  dp[0]=0;//设置初始值
  for(int i=1;i<=sum;i++){
      dp[i]=Integer.MAX_VALUE;
      for(int j=0;j<=number.length-1;j++)
          if(i>=number[j])
              dp[i]=Math.min(dp[i],dp[i-number[j]]+1);//取最小值
      }
  for (int i = 0; i < sum+1; i++) {
      if(dp[i]==Integer.MAX_VALUE)
      {
          System.out.println("-1");
      }
      else {
          System.out.println(dp[i]);
      }
  }

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇