一个问题js实现
暴力循环求解
function change4() {
var count = 0;
for (let i = 0; i <= (100 / 7); i++) {
for (let j = 0; j <= (100 / 3); j++) {
for (let k = 0; k <= (100 / 2); k++) {
if (i * 7 + j * 3 + k * 2 == 100) {
count += 1;
}
}
}
}
console.log(count);
}
缺点：时间复杂度高可扩展性差，如果是100种货币就需要100层循环
线性规划法
function change3(aim, penny) {
var res = 0;
function _cal(newAim, penny) {
const newPenny = penny.slice(); // 这里一直是用的同一个数组，要拷贝一份，否则循环两次就pop空了
var cur = newPenny.pop();
for (let i = 0, num = newAim/cur; i<= num; i++) {
const left = newAim - cur*i;
if (left === 0) {
res++;
}
else {
newPenny.length > 0 && left > 0 && _cal(left, newPenny)
}
}
}
_cal(aim, penny);
return res;
}
change3(100, [2,3,4]);
缺点：调用栈可能溢出
线性规划法想办法改成循环的方式
TODO
