Acwing.1371 货币系统(完全背包问题)

题目

给定 V种货币(单位:元),每种货币使用的次数不限。

不同种类的货币,面值可能是相同的。

现在,要你用这 V种货币凑出 N元钱,请问共有多少种不同的凑法。

输入格式

第一行包含两个整数 V和 N。

接下来的若干行,将一共输入 V个整数,每个整数表示一种货币的面值。

输出格式

输出一个整数,表示所求总方案数。

数据范围

1≤V≤25

1≤N≤10000

答案保证在long long范围内。

  • 输入样例:
3 10
1 2 5
  • 输出样例:
10

题解

import java.util.Scanner;

/**
 * @author akuya
 * @create 2024-04-02-22:05
 */
public class Main {
    static int V=26;
    static int N=10010;
    static int w[]=new int[26];
    static int v;
    static int n;
    static long f[][]=new long[V][N];

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        v=scanner.nextInt();
        n=scanner.nextInt();
        for(int i=1;i<=v;i++){
            w[i]=scanner.nextInt();
        }

        f[0][0]=1;

        for(int i=1;i<=v;i++){
            for(int j=0;j<=n;j++){
                f[i][j]=f[i-1][j];
                if(j-w[i]>=0)
                    f[i][j]+=f[i][j-w[i]];
            }
        }


        System.out.println(f[v][n]);

    }
}

思路

这道题是一道典型的背包问题,如果大家连背包问题都不了解的话得赶快去搜索点点资料扩充自己的知识点了,因为背包问题作为DP问题中较为基础且典型的题目,大家掌握之后才能对DP有更深入的理解,最其他题才能有最基本的思路。

这道题我们可以把总金额看成背包容量,货币面额等于物体总量。不限制物体数量只有重量,标准的完全背包问题,大家只需要将完全背包问题的代码改一改即可。

完全背包问题和各种背包问题可以改变代码从而优化空间,但那个是在太难理解,博主当初看y总视屏觉得懂了,但实际上过了一段时间就忘得一干二净写不出来。还是这种不节约空间但很容易看懂逻辑的代码适合我(我是菜鸡)。

大家如果想理解去看y总的算法基础课,博主没有那个实力讲解TWT。

这道题的基本逻辑还是“状态转移方程”和“集合”,比较特别的是完全背包问题的状态转移方程需要通过一定的数学计算优化,不然要超时,大家看下图即可。

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/510786.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C#常见Winform窗体效果

目录 1&#xff0c;窗体闪烁。 2&#xff0c;透明非矩形的窗体。 3&#xff0c;窗口显示&#xff0c;退出呈现平滑效果。 4&#xff0c;窗体不在任务栏中显示&#xff1a; 1&#xff0c;窗体闪烁。 /// <summary>/// 窗体闪烁/// </summary>/// <param na…

提质增效|大型汽车制造业运维精细化管理建设实战

项目背景 某大型汽车制造企业随着数字化技术的深入应用&#xff0c;对运维在“质量与效率”方面的精细化管理有了更高的要求。借助云智慧运维指标体系实现了 IT 架构的智能化与可视化&#xff0c;高效解决系统显性问题&#xff0c;积极处理系统隐性问题&#xff0c;提升系统稳…

AttributeError: ‘TestBrowser‘ object has no attribute ‘driver‘

求助大佬&#xff01;&#xff01; 求助大佬&#xff01;&#xff01; 求助大佬&#xff01;&#xff01; AttributeError: TestBrowser object has no attribute driver 代码&#xff1a; test_browser.py from time import sleepfrom appium import webdriverclass Test…

【xinference】(8):在autodl上,使用xinference部署qwen1.5大模型,速度特别快,同时还支持函数调用,测试成功!

1&#xff0c;关于xinference Xorbits Inference (Xinference) 是一个开源平台&#xff0c;用于简化各种 AI 模型的运行和集成。借助 Xinference&#xff0c;您可以使用任何开源 LLM、嵌入模型和多模态模型在云端或本地环境中运行推理&#xff0c;并创建强大的 AI 应用。 Xor…

ChatGPT常用提示词,各行各业如何使用ChatGPT

常规交互提示词&#xff1a; 定义与解释&#xff1a; 请解释XXX术语的含义。阐述一下YYY的概念。 问答模式&#xff1a; 谁是发明了WWW的人&#xff1f;请告诉我太阳系内最大的行星是哪个&#xff1f; 创作类任务&#xff1a; 为我写一首诗&#xff0c;主题是春天的早晨。创作一…

手搓Docker-Image-Creator(DIC)工具(04):DIC的代码实现

此系列的前 3 篇主要是介绍了 Docker 的应用、Docker 编排文件 Dockerfile 的常用命令、以及 Docker 镜像的构建过程等都进行简单介绍。尤其在第 3 篇&#xff0c;讲述了 Docker 运行时、安装用等资源&#xff0c;并在文末提出了存在的不足和改进的方向&#xff0c;本篇就直接从…

安卓Android 架构模式及UI布局设计

文章目录 一、Android UI 简介1.1 在手机UI设计中&#xff0c;坚持的原则是什么1.2 安卓中的架构模式1.2.1 MVC (Model-View-Controller)设计模式优缺点 1.2.2 MVP(Model-View-Presenter)设计模式MVP与MVC关系&#xff1a; 1.2.3 MVVM(Model—View—ViewModel ) 设计模式1.2.4 …

Go项目结构整洁实现|GitHub 3.5k

一、前言 hi&#xff0c;大家好&#xff0c;这里是白泽。今天给大家分享一个GitHub &#x1f31f; 3.5k 的 Go项目&#xff1a;go-backend-clean-arch https://github.com/amitshekhariitbhu/go-backend-clean-architecture 这个项目是一位老外写的&#xff0c;通过一个 HTT…

【MySQL】DML的表操作详解:添加数据&修改数据&删除数据(可cv例题语句)

前言 大家好吖&#xff0c;欢迎来到 YY 滴MySQL系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C Linux的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的…

FastAPI Web框架教程 第6章 表单和上传文件

6-1 什么是Form表单 需求场景 很多网站都支持上传文件&#xff0c;比如说&#xff1a;注册时上传头像&#xff1b;填写问卷时上传附件等等。 那么FastAPI是如何来解决文件上传的需求呢&#xff1f; 其实&#xff0c;这个需求不是FastAPI要解决的问题&#xff0c;这是很常见…

阿赵UE学习笔记——23、动画蒙太奇

阿赵UE学习笔记目录   大家好&#xff0c;我是阿赵。   继续学习虚幻引擎的使用方法。上一篇介绍了动画合成功能&#xff0c;这次介绍的动画蒙太奇&#xff0c;和动画合成有很多类似的东西&#xff0c;但本质上却又不同。   蒙太奇是法语“剪接”的意思。所以动画蒙太奇&…

ARM FVP平台的terminal窗口大小如何设置

当启动ARM FVP平台时&#xff0c;terminal窗口太小怎么办&#xff1f;看起来非常累眼睛&#xff0c;本博客来解决这个问题。 首先看下ARM FVP平台对Host主机的需求&#xff1a; 通过上图可知&#xff0c;UART默认使用的是xterm。因此&#xff0c;我们需要修改xterm的默认字体设…

STM32 M3内核寄存器概念

内容主要来自<<M3内核权威指南>> 汇编程序中的最低有效位&#xff08;Least Significant Bit&#xff09;。LSB是二进制数中最右边的位&#xff0c;它代表了数值中的最小单位。在汇编程序中&#xff0c;LSB通常用于表示数据的最小精度或者作为标志位。 ---------…

element-ui 修改el-form-item样式

文章目录 form结构修改el-form-item所有样式只修改label只修改content只修改input只修改button form结构 <el-form :model"formData" label-width"80px"> <el-form-item label"label1"> <el-input v-model"formData.valu…

新手如何用Postman做接口自动化测试

1、什么是自动化测试 把人对软件的测试行为转化为由机器执行测试行为的一种实践。 例如GUI自动化测试&#xff0c;模拟人去操作软件界面&#xff0c;把人从简单重复的劳动中解放出来&#xff0c;本质是用代码去测试另一段代码&#xff0c;属于一种软件开发工作&#xff0c;已…

二叉树 - 栈 - 计数 - leetcode 331. 验证二叉树的前序序列化 | 中等难度

题目 - 点击直达 leetcode 331. 验证二叉树的前序序列化 | 中等难度1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理方法1&#xff1a;栈方法2&#xff1a;计数 3. 时间复杂度 3. 代码实现方法1&#xff1a;栈方法2&#xff1a;计数 leetcode 331. 验证二…

免费Linux系统和生信宝典原创学习教程

免费Linux系统和生信宝典原创学习教程 生物信息的学习离不开Linux系统&#xff0c;不管自己写命令处理数据&#xff0c;还是使用现有的工具。Linux对我们来讲最重要的是它强大的命令行功能&#xff0c;可以快速、批量、灵活的处理数据的提取、统计和整理等耗时耗力的重复性工作…

CTF wed安全 (攻防世界)练习题

一、disabled_button 步骤一&#xff1a;进入网站发现按钮按不了 步骤二&#xff1a;按F12会查看源代码&#xff0c;会发现disabled disable属性 在HTML中&#xff0c; disabled 属性只有两个值&#xff1a;一个是不带值&#xff08;例如&#xff1a;disabled&#xff09;&…

4.2学习总结

一.java学习总结 (本次java学习总结,主要总结了抽象类和接口的一些知识,和它们之间的联系和区别) 一.抽象类 1.1定义: 抽象类主要用来抽取子类的通用特性&#xff0c;作为子类的模板&#xff0c;它不能被实例化&#xff0c;只能被用作为子类的超类。 2.概括: 有方法声明&…

【隐私计算实训营008——SCQL】

1.SCQL使用/集成最佳实践 目前SCQL只开放API供用户使用/集成 使用SCDBClient上手体验可以基于SCQL API开发封装白屏产品&#xff0c;或集成到业务链路中 1.1 部署系统 环境配置&#xff1a; 机器配置&#xff1a;CPU/MEM最低8C16G机构之间的网络互通 镜像&#xff1a;secret…