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

本文主要是介绍组成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(有限张,重复牌视为相同)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---