首页 > 代码库 > 1 2 5 10 20 --> 800
1 2 5 10 20 --> 800
用1元 2元 5元 10元 20元的钞票凑成800元的方法种数计算，使用了动态规划。
结果没打出来，只是保留在函数里各个vector中，调试可看所有结果。
优点：快
缺点：占空间占内存
耗时时间测试：
和为200：0.0022153191s
和为800：0.025958383s
和为1600：0.062776931s
和为3200：0.18964779s
下面是详细代码，能正常运行算出结果，改进空间很大，只列了思路。
算法为王，C写的O(n2)函数再快也不如R写的O（nlogn)函数。
void CMFCTestDlg::OnBnClickedBegin(){ UpdateData(TRUE); LARGE_INTEGER beginTime; QueryPerformanceCounter(&beginTime); std::vector<int> vec_1_2(m_nTotal+1, -1); for(int i=0; i<=m_nTotal; i++) { vec_1_2[i] = 1+i/2; // 使用1元 2元纸币组合成 0到m_nTotal 元的方法数 } std::vector<int> vec_1_2_5(vec_1_2.begin(), vec_1_2.end()); for(int i=5; i<=m_nTotal; i++) { for(int j=1; j<=i/5; j++) { vec_1_2_5[i] += vec_1_2[i-j*5]; // 使用1元 2元 5元纸币组合成 0到m_nTotal 元的方法数 } } std::vector<int> vec_1_2_5_10(vec_1_2_5.begin(), vec_1_2_5.end()); for(int i=10; i<=m_nTotal; i++) { for(int j=1; j<=i/10; j++) { vec_1_2_5_10[i] += vec_1_2_5[i-j*10]; // 使用1元 2元 5元 10元纸币组合成 0到m_nTotal 元的方法数 } } std::vector<int> vec_1_2_5_10_20(vec_1_2_5_10.begin(), vec_1_2_5_10.end()); for(int i=20; i<=m_nTotal; i++) { for(int j=1; j<=i/20; j++) { vec_1_2_5_10_20[i] += vec_1_2_5_10[i-j*20]; // 使用1元 2元 5元 10元 20元纸币组合成 0到m_nTotal 元的方法数 } }
//.... 如果有50元 100元等更多要求，在此处依次添加即可，很容易扩展
LARGE_INTEGER endTime; QueryPerformanceCounter(&endTime); LARGE_INTEGER frequency; QueryPerformanceFrequency(&frequency); float fTime = (endTime.QuadPart-beginTime.QuadPart)/(float)(frequency.QuadPart); fTime = 0;}
1 2 5 10 20 --> 800
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。