[编程题]换钱的最少货币数
- 热度指数：8741 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
输入描述:
输入包括两行，第一行两个整数n（0<=n<=1000）代表数组长度和aim（0<=aim<=5000），第二行n个不重复的正整数，代表arr。
输出描述:
输出一个整数，表示组成aim的最小货币数，无解时输出-1.
示例1
输入
3 20 5 2 3
输出
4
说明
20=5*4
示例2
输入
3 0 5 2 3
输出
0
示例3
输入
2 2 3 5
输出
-1
备注:
时间复杂度，空间复杂度
。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//第一想法：暴力搜索，过程是先从大到小sort钱币数组，去数组第一个最大值可取得的最多张钱，然后贪心的后找剩余钱，若找不到；
//逐步回溯到上次，减少取钱的数目，若回溯到了最开始的地方，且都没找到，取第二大的值，进行同样操作；
//递归设计，设minMoney为给定了钱币数组arr，从cur开始取钱，取total数目的钱的最少货币数。
int minMoney1(const vector<int> &arr, int cur, int total)
{
for(int i=cur; i<arr.size(); ++i)
{
int num = total / arr[i]; //当前取多少钱
int resi = total % arr[i]; //还剩多少要取；
if(num==0) return minMoney1(arr, cur+1, total);
if(resi==0)
return num; //已经取完了；
else
return num + minMoney1(arr, cur+1, resi);
}
return -1;
}
//不用先sort钱币数组arr的暴力搜索:
int process(const vector<int> &arr, int i, int rest)
{
if(i == arr.size())
return (rest==0) ? 1: 0;
//最少张数，初始为-1，因为还没有找到有效解
int res = -1;
//一次使用卡片k张；
for(int k=0; k*arr[i]<=rest; k++)
{
int next = process(arr, i+1, rest - k*arr[i]);
if(next != -1)//说明这个过程有效
res = res == -1 ? next+k: min(res, next+k);
}
return res;
}
//dp:无后效性：前面用了x张面值为t1的钱币，用了y张面值为t2的钱币；x*t1==y*t2,此时后续的搜索是同样的结果，因此无后效性；
//cur的范围:从0<=cur<=N,即迭代所有的面值；total的范围:从0<=total<=total；
//每行是迭代的面值，每列是迭代的剩余值，面值从0取到N结束，再判断是都是有效的，也就是最后的剩余值为0，即DP[N][0]处；
//最终状态：有效位置dp[N][0]处为0,其余部分是-1；dp[0][total]为题目要求的结果；
int minMoney2(const vector<int> &arr, int total)
{
int N = arr.size();
vector< vector<int>> dp(N+1,vector<int>(total+1, 0));
//设置最后一排的值
for(int i=1; i<=total; ++i)
dp[N][i] = -1;
for(int i=N-1; i>=0; --i) //最后一排是已知状态，没次向上计算;
{
for(int rest=0; rest<=total; ++rest)
{
dp[i][rest] = -1; //先置位默认-1；
if(dp[i+1][rest] != -1){ // 有效位置
dp[i][rest] = dp[i+1][rest];
}
//如果左边的位置不越界且有效
if(rest-arr[i]>=0 && dp[i][rest-arr[i]] != -1){
if(dp[i][rest] == -1){ //之前下面的值为无效的值
dp[i][rest] = dp[i][rest-arr[i]] + 1;
}else{
dp[i][rest] = min(dp[i][rest], dp[i][rest-arr[i]] + 1);
}
}
}
}
return dp[0][total];
}
//单行迭代更新：只需要拿走上面代码中的[i]循环，并且记录上一次里rest的值：dp[i][rest] = dp[i+1][rest];
int minMoney3(const vector<int> &arr, int total)
{
int N = arr.size();
vector<int> dp(total+1, 0);
for(int i=1; i<=total; ++i)
dp[i] = -1;
for(int i=N-1; i>=0; --i) //每次更新一行
{
for(int rest=0; rest<=total; ++rest) //一行一共total列
{
int tmp = dp[rest]; //上一轮的rest处的结果
dp[rest] = -1; //先置位默认-1；
if(tmp != -1){
dp[rest] = tmp;
}
if(rest-arr[i]>=0 && dp[rest-arr[i]]!= -1){
if(dp[rest] == -1)
dp[rest] = dp[rest-arr[i]] + 1;
else
dp[rest] = min(dp[rest], dp[rest-arr[i]] +1);
}
}
}
return dp[total];
}
int main()
{
int length, aim;
cin >> length >> aim;
if(length==0 || aim<0)
return 0;
vector<int> arr(length, 0);
for(int i=0; i<length; ++i)
cin >> arr[i];
cout << minMoney3(arr, aim) << endl;
}
发表于 2019-08-23 22:14:52
回复(4)
典型的完全背包问题：
#include <iostream>
#include <queue>
#include <string>
#include <climits>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
int main() {
//freopen("in", "r", stdin);
int n,V;
cin>>n>>V;
vector<long long> dp(V+1, INT_MAX);
dp[0] = 0;
for(int i = 1;i<=n;i++) {
long long cost;
cin>>cost;
for(int v = cost; v<=V;v++){
dp[v] = min(dp[v - cost] + 1, dp[v]);
}
}
if(dp[V]==INT_MAX) cout<< -1 <<endl;
else cout<<dp[V]<<endl;
return 0;
}
发表于 2020-02-04 10:48:10
回复(1)
#include <stdio.h>
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
int main(void) {
int n, aim;
scanf("%d %d", &n, &aim);
if (n == 0) printf("%d\n", -1);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
}
int tmp;
int dp[aim + 1];
dp[0] = 0;
for (int i = n - 1; i >= 0; i--) {
for (int rest = 1; rest <= aim; rest++) {
tmp = -1;
if (rest - arr[i] >= 0 && dp[rest - arr[i]] != -1) {
tmp = 1 + dp[rest - arr[i]];
}
if (i != n-1 && dp[rest] != -1) {
tmp = tmp == -1 ? dp[rest] : MIN(tmp, dp[rest]);
}
dp[rest] = tmp;
}
}
printf("%d\n", dp[aim]);
return 0;
}
发表于 2022-01-28 15:32:12
回复(0)
在想出用动态规划表dp来求解后，本题的关键在于推演出单元格dp[i][j]的计算公式：
首先，dp[i][j]表示用arr[0...i]范围内的任意货币，组成j元所用的最少数目
产生dp[i][j]可能的情况有：
1. 不用arr[i]面值时，只用arr[0...i - 1]范围的货币时，dp[i][j] = dp[i - 1][j];
2. 在arr[i]面值不超过j的前提下，即arr[i] < j，此时dp[i][j] = dp[i - 1][j - k * arr[i]] + k , k >= 1
即，用k张arr[i]以及arr[0...i - 1]时组成j;
综合上面2种情况，即dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - k * arr[i]] + k)，k >= 1 // (1)
在上面的公式中，只有dp[i - 1][j - k * arr[i]] + k，k >= 1 还需要推导成准确的表达式
dp[i - 1][j - k * arr[i]] + k = dp[i - 1][j - arr[i] - m * arr[i]] + m + 1，m >= 0 // (2)
类似于求dp[i][j]的过程，可以知道dp[i][j - arr[i]] = min(dp[i - 1][j - m * arr[i]]) + m，m >= 0，即
用arr[0...i]的货币组成j-arr[i]所用的最少货币数，其可能值来自于
1. 不适用arr[i]货币，即 dp[i - 1][j - arr[i]]
2. 使用1张以上arr[i]，即 dp[i - 1][j - n * arr[i]] + n, n >= 1
从dp[i][j - arr[i]] = min(dp[i - 1][j - m * arr[i]]) + m，m >= 0 可知，
dp[i - 1][j - arr[i] - m * arr[i]] + m + 1 >= dp[i][j - arr[i]] + 1 // (3)
结合(1)(2)(3)式可得 dp[i][j] = min(dp[i - 1][j], dp[i][j - arr[i]] + 1) // (4)
即dp[i][j]的取值由它在dp表中的上方和左侧的值确定
(2)(3)式的推导是本题的关键
const [n, aim] = readline().split(' ').map(Number);
const arr = readline().split(' ').map(Number);
function initDimensionTwoArray(rNum, cNum) {
const res = [];
for (let i = 0; i < rNum; i++) {
const row = [];
for (let j = 0; j < cNum; j++) {
row.push(Number.MAX_SAFE_INTEGER);
}
res.push(row);
}
return res;
}
// 初始化一个二维dp表，并初始化每个单元格的值为0
const dp = new Array(aim + 1).fill(0);
// 初始化dp表第一行，只用arr[0]的面值找出0...aim的货币所用的最少张数
// 显然，arr[0]只能找它的倍数的货币
for (let j = 1; j < aim + 1; j++) {
dp[j] = Number.MAX_SAFE_INTEGER;
if (j >= arr[0] && dp[j - arr[0]] !== dp[j]) {
dp[j] = dp[j - arr[0]] + 1;
}
}
for (let i = 1; i < n; i++) {
for (let j = 1; j < aim + 1; j++) {
let max = Number.MAX_SAFE_INTEGER;
if (j >= arr[i] && dp[j - arr[i]] !== max) {
max = dp[j - arr[i]] + 1;
}
dp[j] = Math.min(max, dp[j]);
}
}
console.log(dp[aim] !== Number.MAX_SAFE_INTEGER ? dp[aim] : -1);
发表于 2021-02-01 21:38:11
回复(0)
import java.io.*;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str = reader.readLine().split(" ");
int[] arr = parse(str,2);
int n = arr[0];
int amount = arr[1];
arr = parse(reader.readLine().split(" "),n);
reader.close();
System.out.println(coinChange(arr,amount));
}
private static int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
private static int[] parse(String[] str,int len){
int[] arr = new int[len];
for(int i= 0;i < len;++i){
arr[i] = Integer.parseInt(str[i]);
}
return arr;
}
}
发表于 2021-01-29 13:41:21
回复(0)
以示例1输入为例：
时间复杂度O(n*aim)，空间复杂度压缩至O(aim)。
import java.util.*;
public class P189 {
public static int process(int[] arr, int N, int aim) {
int[] dp = new int[aim + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = N - 1; i >= 0; i--) {
for (int rest = 0; rest <= aim; rest++) {
if (rest - arr[i] >= 0 && dp[rest - arr[i]] != -1) {
if (dp[rest] != -1) {
dp[rest] = Math.min(dp[rest], dp[rest - arr[i]] + 1);
} else {
dp[rest] = dp[rest - arr[i]] + 1;
}
}
}
}
return dp[aim];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int aim = sc.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
System.out.println(process(arr, N, aim));
}
}
发表于 2020-05-13 07:07:22
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int length, aim;
cin >> length >> aim;
if(length==0 || aim<0)
return 0;
vector<int> arr(length, -1);
for(int i=0; i<length; ++i)
cin >> arr[i];
vector<int> dp(aim+1, -1);
dp[0] = 0;
for(int i = 1; i < aim+1; i++){
if(i % arr[0] == 0)
dp[i] = i / arr[0];
}
for(int i = 1; i < length; i++){
for(int j = 1; j < aim+1; j++){
if(j < arr[i])
continue;
else if(dp[j-arr[i]] != -1 && dp[j] != -1){
dp[j] = min(dp[j], dp[j-arr[i]]+1);
}
else if(dp[j-arr[i]] != -1){
dp[j] = dp[j-arr[i]]+1;
}
else
continue;
}
}
cout << dp[aim];
}
动态规划，12ms
编辑于 2020-05-06 13:02:02
回复(0)
自上而下dp分析
#include <iostream>
(720)#include <vector>
using namespace std;
int chargecoin(vector<int>& n,int aim){
int MAX = 99999;
int len = n.size();
if (aim <= 0 || len == 0){
return -1;
}
vector<vector<int> > dp(len,vector<int>(aim + 1,0));
//首行初始化
for (int i = 1;i <= aim;i++){
dp[0][i] = MAX;
if (i >= n[0] && dp[0][i - n[0]] != MAX){
dp[0][i] = dp[0][i - n[0]] + 1;
}
}
//逐行进行动态规划
for (int i = 1;i < len;i++){
for (int j = 1;j <= aim;j++){
int rest = MAX;
if (j >= n[i] && dp[i][j - n[i]] != MAX){
rest = dp[i][j - n[i]] + 1;
}
dp[i][j] = min(dp[i - 1][j],rest);
}
}
//返回最少货币数，无解的情况下返回 -1
return dp[len - 1][aim] == MAX ? -1 : dp[len - 1][aim];
}
int main(){
int n,aim;
int result = 0;
cin >> n >> aim;
vector<int> nums(n);
for (int i = 0;i < n;i++){
cin >> nums[i];
}
cout << chargecoin(nums,aim) << endl;
return 0;
}
发表于 2020-04-05 00:19:03
回复(1)
背包问题，动态规划，滚动数组
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int n,aim;
cin>>n>>aim;
int a[n];
int dp[aim+1];
for(int i=0;i<n;i++){
cin>>a[i];
}
dp[0] = 0;
for(int i=1;i<=aim;i++){
if(i>=a[0]&&(i%a[0]==0)){
dp[i] = (i/a[0]);
}else{
dp[i] = -1;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=aim;j++){
if(j>=a[i]){
if(dp[j-a[i]]==-1)
dp[j] = dp[j];
else if(dp[j]==-1)
dp[j] = dp[j-a[i]]+1;
else
dp[j] = min(dp[j],dp[j-a[i]]+1);
}
}
}
cout<<dp[aim]<<endl;
return 0;
}
发表于 2020-01-05 07:23:52
回复(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, x;
cin>>n>>m;
int dp[m+1];
fill(dp,dp+m+1,INT_MAX);
dp[0] = 0;
for(int i=0;i<n;i++){
cin>>x;
for(int j=x;j<=m;j++)
dp[j] = min(dp[j], dp[j-x]+1);
}
cout<<(dp[m]==INT_MAX?-1:dp[m])<<endl;
return 0;
}
发表于 2020-02-06 01:52:36
回复(4)
动态规划求解：
dp[x]表示凑出x金额时的最优解，外层循环是各个面额的钱coins[i]，内层循环就是目标金额j。可以知道，在遍历不同面额coins[i]时，如果我们选择coins[i]这个面额，那我们就是在dp[j-coins[i]]的最优解上加一个coins[i]面额的钱，否则就还是之前的值dp[j]不变。于是写出状态转移方程：dp[j] = min(dp[j], dp[j - coins[i]] + 1)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().trim().split(" ");
int n = Integer.parseInt(params[0]), target = Integer.parseInt(params[1]);
String[] strArr = br.readLine().trim().split(" ");
int[] coins = new int[n];
for(int i = 0; i < n; i++) coins[i] = Integer.parseInt(strArr[i]);
int[] dp = new int[target + 1];
Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);
for(int coin: coins){
for(int j = coin; j <= target; j++)
if(dp[j - coin] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
System.out.println(dp[target] == Integer.MAX_VALUE? -1: dp[target]);
}
}
发表于 2021-06-14 09:41:54
回复(0)
N, K = list(map(int, input().split()))
nums = list(map(int, input().split()))
dp = [float('inf')]*(K+1)
dp[0] = 0
for i in range(1, K+1):
for j in range(N):
if i < nums[j]:
continue
dp[i] = min(dp[i], dp[i-nums[j]]+1)
if dp[K] == float('inf'):
print(-1)
else:
print(dp[K])
发表于 2019-08-24 11:00:04
回复(0)
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int n = Integer.valueOf(s[0]);
int target = Integer.valueOf(s[1]);
int[] dp = new int[target+1];
int[] arr = new int[n];
// dp[i] = max(dp[target-arr[0]],dp[target-arr[1]],...)
s = reader.readLine().split(" ");
for(int i=0;i<n;i++){
arr[i] = Integer.valueOf(s[i]);
}
for(int i=1;i<target+1;i++){
int tmp = -1;
for(int j=0;j<n;j++){
if(i-arr[j] < 0 || dp[i-arr[j]] == -1){
continue;
}
else {
if(tmp==-1)
tmp = dp[i-arr[j]] + 1;
tmp = Math.min(dp[i-arr[j]]+1,tmp);
}
}
dp[i] = tmp;
}
System.out.println(dp[target]);
}
}
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int n = Integer.valueOf(s[0]);
int target = Integer.valueOf(s[1]);
int[] dp = new int[target+1];
int[] arr = new int[n];
// dp[i] = max(dp[target-arr[0]],dp[target-arr[1]],...)
s = reader.readLine().split(" ");
for(int i=0;i<n;i++){
arr[i] = Integer.valueOf(s[i]);
}
for(int i=1;i<target+1;i++){
int tmp = -1;
for(int j=0;j<n;j++){
if(i-arr[j] < 0 || dp[i-arr[j]] == -1){
continue;
}
else {
if(tmp==-1)
tmp = dp[i-arr[j]] + 1;
tmp = Math.min(dp[i-arr[j]]+1,tmp);
}
}
dp[i] = tmp;
}
System.out.println(dp[target]);
}
}
发表于 2022-08-11 22:34:34
回复(0)
采用动态规划，如果采用回溯，复杂度太高
#include "bits/stdc++.h"
using namespace std;
int main()
{
int len;cin>>len;
int target;cin>>target;
vector<int> nums(len);
for(int i=0;i<len;i++)cin>>nums[i];
sort(nums.begin(),nums.end(),greater<int>());
vector<int> ret(target+1,INT_MAX);
ret[0]=0;
for(int i=0;i<=target;i++)
{
for(int j=0;j<len;j++)
{
if(i-nums[j]>=0&&ret[i-nums[j]]!=INT_MAX)
{
ret[i]=min(ret[i],ret[i-nums[j]]+1);
}
}
}
if(ret[target]==INT_MAX) cout<<-1;
else cout<<ret[target];
return 0;
}
发表于 2022-01-28 22:31:17
回复(0)
n,m=input().split() l=list(map(int,input().split())) n=int(n) m=int(m) l.sort() def fun(n,m,l): if m==0: return 0 if m<l[0]: return -1 dp=[0 for i in range(m+1)] #dp[0]=0 for i in range(n): a=l[i] if a>m: break dp[a]=1 for j in range(a+1,m+1): if dp[j-a]>0: if dp[j]==0: dp[j]=dp[j-a]+1 else: dp[j]=min(dp[j],dp[j-a]+1) if dp[m]>0: return dp[m] else: return -1 print(fun(n, m, l))
编辑于 2021-06-08 14:52:45
回复(0)
#include <iostream>
#include <limits.h>
#include <vector>
#include <algorithm>
using namespace std;
int process(int i, int rest, const vector<int>& v){
if(rest < 0)
return -1;
if(rest == 0)
return 0;
//rest > 0
if(i == v.size())
return -1;
//rest > 0 i < v.size()
int minVal = INT_MAX;
for(int num = 0; num * v[i] <= rest; num++){
int tmp = process(i + 1, rest - num * v[i], v);
if(tmp != -1)
minVal = min(tmp + num, minVal);
}
return minVal == INT_MAX ? -1 : minVal;
}
int way1(int aim, const vector<int>& v){
return process(0, aim, v);
}
int main(void){
int n, aim;
cin >> n >> aim;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
cout << way1(aim, v) << endl;
return 0;
}
暴力递归解法
#include <iostream>
#include <limits.h>
#include <vector>
#include <algorithm>
using namespace std;
int way3(int aim, const vector<int>& v){
vector<vector<int>> dp(v.size() + 1, vector<int>(aim + 1, -1));
for(int i = 0; i <= v.size(); i++)
dp[i][0] = 0;
for(int rest = 1; rest <= aim; rest++)
dp[v.size()][rest] = -1;
for(int i = v.size() - 1; i >= 0; i--){
for(int rest = 1; rest <= aim; rest++){
int minVal = INT_MAX;
for(int num = 0; num * v[i] <= rest; num++){
int tmp = dp[i + 1][rest - num * v[i]];
if(tmp != -1)
minVal = min(tmp + num, minVal);
}
dp[i][rest] = minVal == INT_MAX ? -1 : minVal;
}
}
return dp[0][aim];
}
int main(void){
int n, aim;
cin >> n >> aim;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
cout << way3(aim, v) << endl;
return 0;
} 不做斜率优化的递归解法#include <iostream>
#include <limits.h>
#include <vector>
#include <algorithm>
using namespace std;
int way3(int aim, const vector<int>& v){
vector<vector<int>> dp(v.size() + 1, vector<int>(aim + 1, -1));
for(int i = 0; i <= v.size(); i++)
dp[i][0] = 0;
for(int rest = 1; rest <= aim; rest++)
dp[v.size()][rest] = -1;
for(int i = v.size() - 1; i >= 0; i--){
for(int rest = 1; rest <= aim; rest++){
int minVal = INT_MAX;
if(dp[i + 1][rest] != -1)
minVal = min(minVal, dp[i + 1][rest]);
if(rest - v[i] >= 0 && dp[i][rest - v[i]] != -1)
minVal = min(minVal, dp[i][rest - v[i]] + 1);
dp[i][rest] = minVal == INT_MAX ? -1 : minVal;
}
}
return dp[0][aim];
}
int main(void){
int n, aim;
cin >> n >> aim;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
cout << way3(aim, v) << endl;
return 0;
} 斜率优化后的递归算法， 主要是这一块进行优化：
int minVal = INT_MAX;
if(dp[i + 1][rest] != -1)
minVal = min(minVal, dp[i + 1][rest]);
if(rest - v[i] >= 0 && dp[i][rest - v[i]] != -1)
minVal = min(minVal, dp[i][rest - v[i]] + 1);
dp[i][rest] = minVal == INT_MAX ? -1 : minVal;
if(dp[i + 1][rest] != -1)
minVal = min(minVal, dp[i + 1][rest]);
if(rest - v[i] >= 0 && dp[i][rest - v[i]] != -1)
minVal = min(minVal, dp[i][rest - v[i]] + 1);
dp[i][rest] = minVal == INT_MAX ? -1 : minVal;
编辑于 2021-06-02 15:31:35
回复(0)
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] words = br.readLine().trim().split(" ");
//钱币种类个数
int n = Integer.parseInt(words[0]);
//要凑成的金额总数
int amount = Integer.parseInt(words[1]);
String[] words2 = br.readLine().trim().split(" ");
int[] coins = new int[n];
// 构建钱币的整型数组
for(int i=0; i<n; i++){
coins[i] = Integer.parseInt(words2[i]);
}
// 动态转移方程dp[i]：总金额为amount的钱至少需要dp[i]个coin才能凑出
int[] dp = new int[amount+1];
// 初始化dp数组
Arrays.fill(dp , 5000);
//base case
dp[0] = 0;
//遍历dp，找到不同的
for(int i=0; i<dp.length; i++){
for(int coin : coins){
if(i-coin<0) continue;
dp[i] = Math.min(dp[i] , dp[i-coin] + 1);
}
}
int res = (dp[amount]==5000)?-1:dp[amount];
System.out.println(res);
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] words = br.readLine().trim().split(" ");
//钱币种类个数
int n = Integer.parseInt(words[0]);
//要凑成的金额总数
int amount = Integer.parseInt(words[1]);
String[] words2 = br.readLine().trim().split(" ");
int[] coins = new int[n];
// 构建钱币的整型数组
for(int i=0; i<n; i++){
coins[i] = Integer.parseInt(words2[i]);
}
// 动态转移方程dp[i]：总金额为amount的钱至少需要dp[i]个coin才能凑出
int[] dp = new int[amount+1];
// 初始化dp数组
Arrays.fill(dp , 5000);
//base case
dp[0] = 0;
//遍历dp，找到不同的
for(int i=0; i<dp.length; i++){
for(int coin : coins){
if(i-coin<0) continue;
dp[i] = Math.min(dp[i] , dp[i-coin] + 1);
}
}
int res = (dp[amount]==5000)?-1:dp[amount];
System.out.println(res);
}
}
发表于 2021-05-24 09:08:51
回复(0)
转化为完全背包求解
/*
* @Description: 换钱的最少货币数
* @Author:
* @Date: 2020-10-26 15:30:58
* @LastEditTime: 2020-10-26 20:03:26
* @LastEditors: Please set LastEditors
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
int MAX = 99999;
int main(){
int n,aim;
cin >> n >> aim;
if(aim <= 0 || n == 0){
return -1;
}
vector<int> dp(aim + 1,MAX);
dp[0] = 0;
int money;
for(int i = 1;i <= n;i++){
cin >> money;
for(int j = money;j <= aim;j++){
dp[j] = min(dp[j], dp[j - money] + 1);
}
}
cout << (dp[aim] == MAX ? -1 : dp[aim]) << endl;
//system("pause");
return 0;
}
发表于 2020-10-26 20:19:40
回复(0)
C++滚动数组
首先，这个题的要求是有问题的，空间复杂度只能压缩到O(aim)，不能压缩到O(n)，因为一般来说aim比n大，所以空间复杂度比要求的高
脑补一个二维数组，行为0-aim的目标值，列为币值数组
d[i][j] 表示在使用前 i 个币值时，要获得目标值 j 需要使用的最小货币数
有递推公式：
d[i][j] = min(d[i-1][j], d[i][j-coin[i]])
d[i-1][j] 为不使用当前币值，获得目标值 j 的最小货币数，在二维数组中当前值紧挨着的正上方
d[i][j-coin[i]] 为使用当前币值，获得目标值 j 的最小货币数， 在二维数组中当前值的左侧某处
由递推公式可知，求解当前值，只和左侧某个值和紧挨的值有关系
所以，可以使用滚动数组来优化
贴个代码摸个鱼
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, aim;
cin>>n>>aim;
if(aim==0){
cout<<0;
return 0;
}
if(n == 0){
cout<<-1;
return 0;
}
vector<int> v(aim+1, -1); // 多一个0元素，避免漏掉5找5这种整倍情况
v[0] = 0;
int coin;
while(n > 0){ // 大循环，每次读入一个币值
--n;
cin>>coin;
for(int i=1;i<=aim;++i){
int diff = i - coin;
if(diff>=0 && v[diff]!=-1) // 如果aim-coin不越界且是能实现的兑换
v[i] = (v[i]>0? min(v[i], 1+v[diff]):1+v[diff]); // 在有效值中找较小的更新当前值
}
}
cout<<v[aim];
return 0;
}
发表于 2020-07-18 13:12:40
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-12-19 23:04:22
-
2022-12-03 20:12:43 -
2022-09-12 01:26:56
-
2022-09-11 17:46:36 -
2022-09-09 19:47:21
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
