Задача по JS: Как сделать перебор возможных вариантов?

Question

Candy weighs X grams, tangerine - Y grams and apple - Z grams.

Need to write a program that will determine how many different versions of gifts weighing exactly W grams can make Santa Claus.

Function should receive four integers X, Y, Z and W.

Function should return a single integer - the number of gift options.


X = 10
Y = 25
Z = 15
W = 40
Result: 3

вот что я смог сделать:

let candy = 10;
let tangerine = 25;
let apple = 15;
let weight = 40;
let num; // the number of gift options 
function Gifts(candy, tangerine, apple, weight) {
  if (candy + tangerine <= weight) {
    num = 1;
  }
  if (candy + apple <= weight) {
    num = 1;
  }
  if (tangerine + apple <= weight) {
    num = 1;
  }
  num = 1 + 1 + 1;
  console.log(num);
}
Gifts();

Answer 1

Если веса большие, то достаточно перебрать количество каждого подарка.

function solve(x, y, z, w) {
    var result = 0
    for(var x_c = 0; x_c <= w / x; ++x_c) {
        for(var y_c = 0; y_c <= w / y; ++y_c) {
            for(var z_c = 0; z_c <= w / z; ++z_c){
                if(x_c * x + y_c * y + z_c * z == w) {
                    result++;
                }
            }
        }
    }
    return result;
}

Если веса не очень большие, то можно написать рюкзак с помощью динамики.

function solve(x, y, z, w) {
    let dp = new Array(w + 1).fill(0);
    dp[0] = 1;
    let p = [x, y, z];
    for(var k = 0; k < 3; ++k) {
        for(var i  = 1; i <= w; i++) {
            if(i >= p[k]) {
                dp[i] += dp[i - p[k]];
            }
        }
    }
    return dp[w];
}

БЛОГ НА HUSL

Задача по JS: Как сделать перебор возможных вариантов?

Ответы (1 шт):