组成aim的方法数3(有限张,重复牌视为相同)

2024-05-26 01:36

本文主要是介绍组成aim的方法数3(有限张,重复牌视为相同),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:arr是货币数组,其中的值都是正数,再给定一个正数aim,每个值都认为是一张货币,认为值相同的货币没有任何不同,返回组成aim的方法数。例如,arr=[1,2,1,1,2,1,2],aim=4,方法,1+1+1+1,1+1+2,2+2,一共3种方法,所以返回3。

way:

//将货币按面值,张数统计出来放到Info中的2个vector中
//coins面值数组,正数且去重
//zhangs 每种面值对应的张数
//arr[index...]所有的面值,每一个面值都可以选择有限张数,组成rest元的方法数。
#include<iostream>
#include<vector>
#include<map>
using namespace std;struct Info
{vector<int>coins;vector<int>zhangs;Info(vector<int>coins, vector<int>zhangs){this->coins=coins;this->zhangs=zhangs;}
};Info getInfo(vector<int>arr)
{int n=arr.size();map<int,int>mp;for(int i=0; i<n; i++){mp[arr[i]]++;}vector<int>coins;vector<int>zhangs;for(auto pa:mp){coins.push_back(pa.first);zhangs.push_back(pa.second);}return Info(coins, zhangs);
}//coins面值数组,正数且去重
//zhangs 每种面值对应的张数
//arr[index...]所有的面值,每一个面值都可以选择有限张数,组成rest元的方法数。
int process(vector<int>coins, vector<int>zhangs, int index, int rest)
{if(index==coins.size()){return rest==0?1:0;}int ways=0;for(int zhang=0; (zhang<=zhangs[index])&&(rest-zhang*coins[index]>=0); zhang++){ways+=process(coins, zhangs, index+1, rest-zhang*coins[index]);}return ways;
}int coinWay(vector<int>arr, int aim)
{//将货币按面值,张数统计出来放到Info中的2个vector中Info info = getInfo(arr);return process(info.coins, info.zhangs, 0, aim);
}

way2:dp版

int dpWay(vector<int>arr, int aim)
{//将货币按面值,张数统计出来放到Info中的2个vector中Info info = getInfo(arr);vector<int>coins=info.coins;vector<int>zhangs=info.zhangs;int N=coins.size();vector<vector<int>>dp(N+1,vector<int>(aim+1));dp[N][0]=1;for(int index=N-1; index>=0; index--){for(int rest=0; rest<=aim; rest++){int ways=0;for(int zhang=0; (zhang<=zhangs[index])&&(rest-zhang*coins[index]>=0); zhang++){ways+=dp[index+1][rest-zhang*coins[index]];}dp[index][rest]=ways;}}return dp[0][aim];
}

这篇关于组成aim的方法数3(有限张,重复牌视为相同)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a