완전 탐색 문제는 어렵네요 강의 보기 전에 하나씩 풀어보는데 졸업선물 문제는 기억에 남아서 올려봅니다.
그리고 강의도 재밌고 효율적으로 생각하는 방식을 잘 알려주시는 거 같습니다.
<script>
function solution(m, product){
class Product{
constructor(product = []){
this._product = product;
}
get price(){
return this._product[0];
}
get fare(){
return this._product[1];
}
disCountCost(){
return this.price / 2 + this.fare;
}
cost(){
return this.price + this.fare;
}
}
class Products{
constructor(products = []) {
this._products = products;
}
get commodities(){
return this._products;
}
get numOfProducts(){
return this.commodities.length;
}
map(transform){
return new Products(transform(this.commodities));
}
totalCost(){
return this.commodities
.map(product =>
product.cost()).reduce((sum, v) => sum + v, 0);
}
}
function possibleCost(products){
return products.commodities
.map((v, i) => [v, products.map(makeDrop(i))])
.map(([v, products]) => v.disCountCost() + products.totalCost())
.reduce((minCost, current) => Math.min(minCost, current));
}
function makeChildren(products){
const total = products.numOfProducts;
return total > 1 ?
products.commodities
.map((_, idx) => products.map(makeDrop(idx))) :
[products];
}
function makeGeneration(depth, products){
if(depth === 0) return [products];
return makeChildren(products)
.map(sub => makeGeneration(depth - 1, sub))
.flat();
}
const makeDrop = i => arr => arr.slice(0,i).concat(arr.slice(i+1));
const commos = new Products(product.map(commo => new Product(commo)));
let limit = commos.numOfProducts;
for(let i = 0; i < limit; i++){
if(makeGeneration(i, commos)
.filter(prod => possibleCost(prod) <= m)
.length > 0) {
return limit - i;
}
}
}
let arr=[[10, 3], [6, 6], [2, 2], [4, 3], [4, 5]];
console.log(solution(28, arr));
</script>
