如何使用非负整数降低线性方程组问题的复杂度

Question

我有一个问题x + 2y + 3z =600。我试图找到这个给定线性方程的所有和组合。我使用了蛮力方法。复杂度为O（n ^ 3）。我对解决方案进行了概括，但复杂度仍然相同。任何人都可以帮助我降低复杂性。

var LoopCounter = 0;
var n =600

for(var x = 0; x <= n; x++){
  for(var y = 0; y <= n-x; y++){
    for(var z = 0; z <= n-(x+(2*y)); z++){
        if(x + (2*y) + (3 * z) == 600){
            console.log("x : " + x + " 2y:" + y + " 3z:" + z);
            count++;
        }
        LoopCounter++;
    }
  }
}

The total number of counts : 30301 
The total number of loops : 18225851

Answer 1

let LoopCounter = 0,
  count = 0;
const n = 600

for (let x = 0; x <= n; x++) {
  const nMinusX = n - x;
  for (let y2 = 0; y2 <= nMinusX; y2 += 2) {
    const z3 = nMinusX - y2;
    // z3 must be a multiple of 3
    if (z3 % 3 === 0) {
      // console.log("x : " + x + " 2y:" + y2/2 + " 3z:" + z3/3);
      count++;
    }
    LoopCounter++;
  }
}
console.log('count:', count, 'Loops:', LoopCounter);
// count: 30301 Loops: 90601