L3-001 凑零钱 深搜

2024-03-29 13:08
文章标签 001 零钱 l3

本文主要是介绍L3-001 凑零钱 深搜,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

L3-001 凑零钱 (30 分)

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 10​4​​ 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。

输入格式:

输入第一行给出两个正整数:N(≤10​4​​)是硬币的总个数,M(≤10​2​​)是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出格式:

在一行中输出硬币的面值 V​1​​≤V​2​​≤⋯≤V​k​​,满足条件 V​1​​+V​2​​+...+V​k​​=M。数字间以 1 个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出 No Solution

注:我们说序列{ A[1],A[2],⋯ }比{ B[1],B[2],⋯ }“小”,是指存在 k≥1 使得 A[i]=B[i] 对所有 i<k 成立,并且 A[k]<B[k]。

输入样例 1:

8 9
5 9 8 7 2 3 4 1

输出样例 1:

1 3 5

输入样例 2:

4 8
7 2 4 3

输出样例 2:

No Solution

要判所有硬币加起来总金额少于m,就没有必要搜了,这个是最后一个点,不写的话只有29分~

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int n,m,a[10005],pre[10005],f;
int out[10005],l=0;
void dfs(int t,int sum)
{//printf("t=%d sum=%d\n",t,sum);if(t==n||f)return;if(sum==m){f=1;while(t!=-1){out[l++]=a[t];t=pre[t];}return;}for(int i=t+1;i<n;i++){if(sum+a[i]<=m){pre[i]=t;dfs(i,sum+a[i]);}//else break;}
}
int main()
{int i,j,s=0;f=0;memset(pre,-1,sizeof pre);scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&a[i]);s+=a[i];}if(s<m)printf("No Solution\n");else{sort(a,a+n);dfs(-1,0);if(f==0)printf("No Solution\n");else{for(i=l-1;i>=0;i--)printf("%d%c",out[i],i==0?'\n':' ');}}	
}

 

这篇关于L3-001 凑零钱 深搜的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858680

相关文章

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

NIFI汉化_替换logo_二次开发_Idea编译NIFI最新源码_详细过程记录_全解析_Maven编译NIFI避坑指南001

由于需要对NFI进行汉化,以及二次开发,首先要下载源码以后编辑通过,NIFI的源码,项目非常多,编译过程中需要编译超过570个jar包,同时编译过程很慢需要30多分钟. 1.首先下载NIFI源码,根据需要下载对应版本: https://github.com/kemixkoo/orchsym-runtime/   首先介绍一下,这个是一个公司根据nifi进行定制开发的,已经汉化,但是不能商

代码随想录:322. 零钱兑换

322. 零钱兑换 class Solution {public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(10005,INT_MAX);//由于后面要取最小值,所以初始大一些dp[0]=0;//总金额为0个数一定为0for(int i=0;i<coins.size();i++){for(int j=coins

JavaSE-易错题集-001

1. AccessViolationException异常触发后,下列程序的输出结果为(      ) 1 2 3 4 5 6 7 8 9 10 11 12 13 static void Main(string[] args)   {       try       {           throw new AccessViolationException();           Con

微信支付商家转账到零钱:快速开通攻略及功能全解

一、申请资格与条件 哪些商家可以申请商家转账到零钱功能? 仅公司性质的商户可以申请,个体工商户当前不支持此功能。商户账号应无正在进行的处罚,且历史无风险行为。微信支付账户没有历史违规记录。商家系统已经上线并可以访问。是否需要满足开通满90天和连续交易30天的要求? 目前商家转账到零钱及现金红包功能已取消该限制,新注册公司可直接申请,无需等待。 二、申请流程 如何申请开通商家转账到零钱功能

线段树 001- 概述

线段树就是一个能高效维护动态区间的一个数据结构; 他能把一个区间分成多个区间,这些区间根据它们的之间的关系形成一个树形结构。 这个过程可以构建出一颗完全二叉树。 其中线段树的操作有:         1.修改         2.查询 比如我们现在要维护一个长度为n的区间的和,那么当n=10的时候,该区间所对应的树为: 可以发现每个节点代表一个区间,每个节点存的是该区间的和;

【Python机器学习】核心数、进程、线程、超线程、L1、L2、L3级缓存

如何知道自己电脑的CPU是几核的,打开任务管理器(同时按下:Esc键、SHIFT键、CTRL键) 然后,点击任务管理器左上角的性能选项,观察右下角中的内核:后面的数字,就是你CPU的核心数,下图中我的是16个核心的。 需要注意的是,下面的逻辑处理器:32 表示支持 32 线程(即超线程技术) 图中的进程:和线程:后面的数字代表什么 在你上传的图片中,“进程:180” 和 “线程:3251”

001:VTK的学习资料与方法

VTK 医学图像处理---VTK学习资料 简介:       本节主要介绍学习VTK的一些资料和学习方法,仅供参考,可以根据自己的实际情况来调整。学习资料主要以VTK官网提供的资料为主,不管对于入门还是深入研究都足够了;但为了让入手VTK的难度更低一点,所以在有了本系列博文。 VTK 医学图像处理---VTK学习资料 简介: 1 官网免费电子书(好像有中文翻译版,建议看原版)

LeetCode 算法:零钱兑换 c++

原题链接🔗:零钱兑换难度:中等⭐️⭐️ 题目 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1: 输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 =