DPメニュー【最安値を達成するには 1 〜 4】
【最安値を達成するには 1】コード
reader.on('close', () => {
const [n, a, b] = lines[0].split(' ').map(Number);
const dp = [0, a]; // 0 個の価格は 0 円, 1個の値段は a 円
for (let i = 2; i <= n; i++) { // ループの範囲は 2 個 ~ n 個
dp[i] = Math.min(dp[i - 1] + a, dp[i - 2] + b); //dp[i]は dp[i - 1] + a 円 と dp[i - 2] + b 円 の安い方
}
console.log(dp[n]);
});
dp[i] の i の値は 購入するリンゴの個数 で i 個のリンゴの価格は i – 1 個の価格 + a 円と i – 2 個の価格 + b 円 を比較して 安い方でした。
【最安値を達成するには 2】コード 1/2
reader.on('close', () => {
const [n, a, b] = lines[0].split(' ').map(Number);
const dp = [0, a]; // 0 個の価格は 0 円, 1個の値段は a 円
for (let i = 2; i <= n; i++) { // ループの範囲は 2 個 ~ n 個
if (i >= 5) { // 5 個以上なら…
dp[i] = Math.min(dp[i - 2] + a, dp[i - 5] + b); // dp[i]は dp[i - 1] + a 円 と dp[i - 5] + b 円 の安い方
} else if (i >= 2) { // 5 個未満, 2 個以上なら…
dp[i] = Math.min(dp[i - 2] + a, b); // dp[i]は dp[i - 1] + a 円 と b 円 の安い方
}
}
console.log(dp[n]);
// console.log(dp);
});解説の解き方と違っていますが こんな感じになりました。
【最安値を達成するには 2】コード 2/2
reader.on('close', () => {
const [n, a, b] = lines[0].split(' ').map(Number);
const dp = new Array(n + 5).fill(10000000);
dp[0] = 0;
for (let i = 1; i < n + 5; i++) {
if (i >= 2) {
dp[i] = Math.min(dp[i], dp[i - 2] + a);
}
if (i >= 5) {
dp[i] = Math.min(dp[i], dp[i - 5] + b);
}
}
// console.log(dp);
console.log(Math.min(...dp.slice(n))); // 解答①
const dp2 = [];
for (let i = n + 4; i >= 0; i--) {
dp2[i] = dp[i];
for (let j = i + 1; j < n + 5; j++) {
dp2[i] = Math.min(dp2[i], dp[j]);
}
}
// console.log(dp2);
console.log(dp2[n]); // 解答②
for (let i = n + 3; i >= 1; i--) {
dp[i] = Math.min(dp[i], dp[i + 1]);
}
// console.log(dp);
console.log(dp[n]); // 解答③
});解答コード例・解説を参照しました。解き方が3通り(解答①〜③)ありますが 出力値は全て同じでした。
【最安値を達成するには 3】コード 1/2
reader.on('close', () => {
const [n, x, a, y, b] = lines[0].split(' ').map(Number);
const dp = [0, a]; // 0 個の価格は 0 円, 1個の値段は a 円
for (let i = 2; i <= n; i++) { // ループの範囲は 2 個 ~ n 個
if (i >= y) { // y 個以上なら…
dp[i] = Math.min(dp[i - x] + a, dp[i - y] + b); // dp[i]は dp[i - x] + a 円 と dp[i - y] + b 円 の安い方
} else if (i >= x) { // y 個未満, x 個以上なら…
dp[i] = Math.min(dp[i - x] + a, b); // dp[i]は dp[i - 1] + a 円 と b 円 の安い方
}else { // x 個未満なら…
dp[i] = a; // dp[i] は a 円
}
}
console.log(dp[n]);
// console.log(dp);
});【STEP: 2】コード 1/2 とほぼ同じです。2 個が a 円で 5 個が b 円
だったのが x 個が a 円で y 個が b 円
になったので 2 → x, 5 → y になりました。
【最安値を達成するには 3】コード 2/2
reader.on('close', () => {
const [n, x, a, y, b] = lines[0].split(' ').map(Number);
const dp = new Array(n + y).fill(10000000);
dp[0] = 0;
for (let i = 1; i < n + y; i++) {
if (i >= 2) {
dp[i] = Math.min(dp[i], dp[i - 2] + a);
}
if (i >= y) {
dp[i] = Math.min(dp[i], dp[i - y] + b);
}
}
// console.log(dp);
console.log(Math.min(...dp.slice(n))); // 解答①
const dp2 = [];
for (let i = n + y - 1; i >= 0; i--) {
dp2[i] = dp[i];
for (let j = i + 1; j < n + y; j++) {
dp2[i] = Math.min(dp2[i], dp[j]);
}
}
// console.log(dp2);
console.log(dp2[n]); // 解答②
for (let i = n + y - 2; i >= 1; i--) {
dp[i] = Math.min(dp[i], dp[i + 1]);
}
// console.log(dp);
console.log(dp[n]); // 解答③
});解答コード例・解説を参照しました。
【最安値を達成するには 4】コード 1/2
reader.on('close', () => {
const [n, x, a, y, b, z, c] = lines[0].split(' ').map(Number);
const dp = [0, a]; // 0 個の価格は 0 円, 1個の値段は a 円
for (let i = 2; i <= n; i++) { // ループの範囲は 2 個 ~ n 個
if (i >= z) { // z 個以上なら…
dp[i] = Math.min(dp[i - x] + a, dp[i - y] + b, dp[i - z] + c); // dp[i]は dp[i - x] + a 円 と dp[i - y] + b 円 と dp[i - z] + c 円の最安
} else if (i >= y) { // z 個未満, y 個以上なら…
dp[i] = Math.min(dp[i - x] + a, dp[i - y] + b, c); // dp[i]は dp[i - x] + a 円 と dp[i - y] + b 円 dp[i - z] + c 円の最安
} else if (i >= x) { // y 個未満, x 個以上なら…
dp[i] = Math.min(dp[i - x] + a, b); // dp[i]は dp[i - x] + a 円 と b 円 の最安
} else { // x 個未満なら…
dp[i] = a; // dp[i] は a 円
}
}
console.log(dp[n]);
// console.log(dp);
});x 個が a 円・y 個が b 円・z 個が c 円
と 購入方法が 3パターンになりました。
【最安値を達成するには 4】コード 2/2
reader.on('close', () => {
const [n, x, a, y, b, z, c] = lines[0].split(' ').map(Number);
const dp = new Array(n + z).fill(10000000);
dp[0] = 0;
for (let i = 1; i < n + z; i++) {
if (i >= x) {
dp[i] = Math.min(dp[i], dp[i - x] + a);
}
if (i >= y) {
dp[i] = Math.min(dp[i], dp[i - y] + b);
}
if (i >= z) { // z 個以上なら…
dp[i] = Math.min(dp[i], dp[i - z] + c);
}
}
// console.log(dp);
console.log(Math.min(...dp.slice(n))); // 解答①
const dp2 = [];
for (let i = n + z - 1; i >= 0; i--) {
dp2[i] = dp[i];
for (let j = i + 1; j < n + z; j++) {
dp2[i] = Math.min(dp2[i], dp[j]);
}
}
// console.log(dp2);
console.log(dp2[n]); // 解答②
for (let i = n + z - 2; i >= 1; i--) {
dp[i] = Math.min(dp[i], dp[i + 1]);
}
// console.log(dp);
console.log(dp[n]); // 解答③
});解答コード例・解説を参照しました。
コメント