首页 > 代码库 > 1 2 5 10 20 --> 800

1 2 5 10 20 --> 800

2024-10-26 23:00:39   210人阅读

用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


联系
我们