l*********y
发帖数: 142 | 1 Given n types of coin denominations of values, makes change for an amount of
money C with as few coins as possible. 找零钱是O(Cn);
今天看到一个print_all_combination 的 implementation, very straightforward,
那位大侠给分析一下复杂度, 这个应该不低于O(Cn)
int cent = 100; // how to make change for 1 dollar with unlimited
// quarter, dime, nickel and cent
int comb = 0; // how many combinations;
for (int i = 0; i <= cent/ 25; i++) {
int cent_q = cent - i * 25;
for (int j = 0; j <= cent_q / 10; j++) {
int cent_d = cent_q - j * 10;
for (int k = 0; k <= cent_d / 5; k++) {
int cent_n = cent_d - k * 5;
cout << i << '\t' << j << '\t' << k << '\t' << cent_n << endl;
comb++;
}
}
} |
|
