Hỏi thuật toán bài toán tìm tổng số cách đổi tiền có thể được

#43

4 vòng for là đủ rồi, java bạn à

2 Likes
#44

Hic!!! chắc em còn phải học hỏi nhiều… :smiley: anyway … bài trên web là done hết rồi :smiley: Cảm ơn bác quân đã nhiệt tình chỉ dẫn em đường đi nước bước ạ :smiley:

1 Like
#45

thử thêm

if (a*m20 + b*m50 + c*m100 + d*m200 + f*m500 > n) break;
#46

Thế thì là nhanh do thuật toán :))

#47

Yep, mình dùng nhiều trick để tối ưu số phép tính nên mới tối ưu được tốc độ như thế, nhưng nói chung đây là kiểu làm trâu bò, không thích hợp với số lớn

1 Like
#48

Share code cho em với nha anh :’( Cùng lớp mà em chưa nghĩ ra cách làm nữa…

#49

viết vậy thì duyệt trâu bao nhiêu loại tiền (mấy vòng for) cũng được nè:

http://rextester.com/WRMQQA93415
cpu time: 0.01 sec

#include <iostream>
#include <algorithm>
#include <vector>

void count(int n, const std::vector<int>& values, int& ways, int& coins, int vid,
           int total=0, int coinCount=0)
{
    if (vid)
        for (; total <= n; total += values[vid], coinCount++)
            count(n, values, ways, coins, vid-1, total, coinCount);
    else if ((n-total) % values[vid] == 0) //khỏi cần vòng for cuối cùng
    {
        ways++;
        coinCount += (n-total) / values[vid];
        coins = coins ? std::min(coins, coinCount) : coinCount;
    }
}

int main()
{
    std::vector<int> values{2,5,10,20,50};
    std::sort(begin(values), end(values));
    
    int n = 1000;
    int ways = 0;
    int coins = 0;
    count(n, values, ways, coins, values.size() - 1);
    std::cout << coins << "\n" << ways << "\n";
}

ai copy thầy hỏi giải thích ko biết giải thích thì rớt nhé :joy:

4 Likes
#52

Có biến coins kìa bạn.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?