NYOJ995硬币找零(简单dp)

简介:

/*
    题意:给你不同面额的硬币(每种硬币无限多),需要找零的面值是T,用这些硬币进行找零,
    如果T恰好能被找零,输出最少需要的硬币的数目!否则请输出剩下钱数最少的找零方案中的最少硬币数!
    
    思路:转换成完全背包的问题! 
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int dp[100005];

int main(){
    int n, v;
    while(cin>>n>>v && (n||v)){
        memset(dp, 0x3f, sizeof(dp));
        dp[0]=0;//不要忘记这一步 
        for(int i=1; i<=n; ++i){
            int k;
            cin>>k;
            for(int j=k; j<=v; ++j)
               dp[j]=min(dp[j], dp[j-k]+1);//这里是min,不是max 
        }
        for(int i=v; i>=0; --i)//如果遇到了找零的数目不是INF,那么就是答案! 
              if(dp[i]!=INF){
                   dp[v]=dp[i];
                 break;
              }
        cout<<dp[v]<<endl;
    } 
    return 0;
}

目录
相关文章
|
6月前
|
Java
hdu 1427 速算24点【暴力枚举】
hdu 1427 速算24点【暴力枚举】
61 0
|
3月前
|
算法
【算法】贪心算法——柠檬水找零
【算法】贪心算法——柠檬水找零
|
5月前
蓝桥杯动态规划-第五弹 最大子数组和 买卖股票最佳时机IV 第N个泰波那契数 环形数组
蓝桥杯动态规划-第五弹 最大子数组和 买卖股票最佳时机IV 第N个泰波那契数 环形数组
|
6月前
|
算法
【贪心算法】|860.柠檬水找零
【贪心算法】|860.柠檬水找零
|
6月前
|
Java
leetcode-860:柠檬水找零
leetcode-860:柠檬水找零
57 0
|
算法 Java Python
深入理解动态规划算法 | 凑硬币
深入理解动态规划算法 | 凑硬币
136 0
|
算法 Java
动态规划算法-凑硬币
动态规划算法-凑硬币
116 0
leetcode 860柠檬水找零
leetcode 860柠檬水找零
63 0
leetcode 860柠檬水找零
|
缓存 算法
钞票找零-贪心,动态规划算法
钞票找零-贪心,动态规划算法
122 1
|
JavaScript 测试技术
最后一块石头的重量Ⅱ(LeetCode-1049)
最后一块石头的重量Ⅱ(LeetCode-1049)
104 0
最后一块石头的重量Ⅱ(LeetCode-1049)