首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

动态规划解决整数划分的问题

前几天去华为做机试,遇到一个整数划分的问题,题目是:现有1,2,5,10,20,50,100 元这几种钱币,问给定n元能有多少种分配方式。例如n=4时,有1+1+1+1  ,1+2+1 , 2+2 三种划分。我解决这道题是从网上看的方法,用的递归,但是悲剧的是测试用例运行超时,结果题没做出来,我直觉上觉得用动态划分可以解决,所以就研究了动态划分的解法。 首先,先找出划分,每种组合以最大面值等于多少就形成一个划分: 例如:现在这道题,有 1 , 2 , 5 ,10 ,20 ,50 , 100这7种划分,每种划分的定义是,m划分代表,在这些钱币中,最大的钱币为m。 找出划分后再找出递推公式,这个递推公式在网上找,一大堆,但是针对这个问题的递推公式为:         n代表钱数,m代表划分数         1. 当n==1或者是m==1时,q(n , m)=1;         2. 当n==m时,q(n ,  m)=q(n,m-1)         3. 当n<m时,q (n , m)=q(n,n)         4. 当n>m时,q(n , m)= q(n ,m-1)+q(n-m,m)i 然后找出初始条件,初始条件就是当n==0,时,所有划分都等于0,所以再二维数组的第一行都为0,二维数组,行代表你的钱数,列数代表的划分数,这些划分的值在一个一维数组中存着,所以二维数组的列代表,上面一维数组的索引。还有就是当1划分的时候,所有值都等于1(二维数组的值就是拆分的个数)。 然后就按照上面的递推公式来填充二维数组,最后返回你钱数的最大划分就是最终结果,我是根据01背包问题研究的这道题,如有不懂请参见经典的01背包问题,如写的不好,请大家多批评,下面是我的代码:直接可以运行出结果 package com.test; public class Main { static int[] qian=new int[]{1,2,5,10,20,50,100}; public static int get(int money){ int[][] test=new int[money+1][7]; for(int i=0;i<test.length;i++){ if(i==0){ for(int j=0;j<qian.length;j++){ test[i][j]=0; } }else{ for(int j=0;j<qian.length;j++){ if(qian[j]==1){ test[i][j]=1; }else{ if(i<qian[j]){ test[i][j]=test[i][j-1]; }else if(i==qian[j]){ test[i][j]=test[i][j-1]+1; }else if(i>qian[j]){ test[i][j]=test[i-qian[j]][j]+test[i][j-1]; } } } } } for(int i=0;i<=money;i++){ for(int j=0;j<qian.length;j++){ System.out.print(test[i][j]+" "); } System.out.println(); } return test[money][qian.length-1]; } public static void main(String[] args) { System.out.println(get(250)); } }

01

数组总结

数组用于关于大量输入各种数据的问题,这时候就不需要一个一个定义,一个数组便可以储存这些数据。 定义一位数组 int a【k】k一定是一个固定的数,不能是定义的变量,如果不用循环的方式输入数组,也可以用类似于cin>>[a++]这样的形式。 #include<string.h> memset(数组名,0,sizeof(数组名)) 即可将数组的数据清零。 数组通常是和循环一起组合来解决问题,通过数组与循环还可以对数据进行排序, 冒泡排序:既相邻的数据进行对比选择出最小的或最大的数据排在最后,每进行一次循环后,上限即可减小一个,因为最后一个的顺序已经排好并且第一次上限应为最大值减一。 选择排序:从首个数据开始,与后面数据比较将最大或最小排在首位,依次进行,每次初始值增一。 插入排序:(必为有序数列)将插入的值排在最后,与前面的值比较,符合条件则交换,不符合便停止。 或则引用sort,头文件为algorithm,该排序为升序,基本格式为sort(a+k,a+l),其中k为排序的第一个数据的位置,l为排序最后一个数据的位置加一。 定义n维数组 定义的方式:p[a][b][c][d][e][f]…abcdef皆为实数,这种类型的数组可以解决分组的大量数据的问题,就例如解决输入矩形的时候就可以用二维数组来解决。多维数组尤其要注意定义的数据量不能太大也不能太小,太小会出现数据溢出,太大会出现程序结束。 在计算数组类的问题要根据数组的特点与题目结合,找出规律,往往可以将问题简化。 向函数传递一维数组,在定义函数的时候类似与传递实数的方式, 既 返回值类型 函数名(数组类型 数组名[ ]),注意传递一维数组方括号内不需要有数值。例: int joy(int a[ ]) {

01
领券