题解 | #购物单#

// 价格与重要度的乘积的总和最大

// j件物品 价格v[j]    重要度为 w[j]  
// 0  1  2 
//使每件物品的价格与重要度的乘积的总和最大
// 第一次审题觉得只要是不超过 goodsTotal元 所得到的价格与重要度的乘积的总和最大觉得是答案
// 忽略了要买goodsCount这个条件，导致用例不通过
// 本题条件就是 满足买够goodsCount个 还要满足买的价格相加不能超过goodsTotal元。还要得到最大的乘积
// 代码通俗易懂不理解的可以留言哦

// 还有一种方法就是将所有的主件，附件 的价格算出来然后得到一件的价格的 价格与重要度的乘积 
// 比如一个主件。主件的价格 - 价格与重要度的乘积  / 1
// 比如一个主件 + 一个附件。主件的价格 + 附件的价格  - 价格与重要度的乘积  / 2
// 全部当成一个主件来看，相当于从n个主件中获取10主件然后得到最大值的集合，有机会的伙伴可以试试。
let line;
let arr = []
let newArr = []
let goodsTotal = 0
let goodsCount = 0
let base = 10
function Goods(item,index){
    let temp = item.split(' ').map(i=>parseInt(i));
    this.goodsPrice = temp[0] / base;
    this.goodsWeight = temp[1];
    this.goodsParent = temp[2];
    this.goodsCode = index;
    this.goodsValue = temp[0] * temp[1]
}
while(line = readline()){
    arr.push(line);
    if(arr.length >= 1){
        let temp = arr[0].split(' ').map(i=>parseInt(i));
         goodsTotal = temp[0];
         goodsCount = temp[1];
        if(arr.length > 1){
            newArr.push(new Goods(line,arr.length - 1));
        }
    }
}

function getRes(arr,goodsCount,goodsTotal){
    let max = 0
//     初始化全部为0元的二维数组
    let dp = new Array(goodsCount + 1).fill(0).map(()=>new Array(goodsTotal + 1).fill(0))
    for(let i = 1;i<=goodsCount;i++){
        for(let j = 0;j<= goodsTotal;j++){
//            当前价格默认等于上一个j元对应的最大 物品的价格与重要度的乘积
            dp[i][j] = dp[i-1][j];
//             附件过滤
            if(arr[i-1].goodsParent != 0){
                continue;
            }
//             初始化当前第 i 个物品不超过 j 元对应的最大物品的价格与重要度的乘积
//             思路就是用当前的最大值 和 上一个减去这次主件对应的最大价格对应的最大值加上这次物品的最大值 取两者之间最大的
            if(j>=arr[i-1].goodsPrice){
                dp[i][j] = Math.max(dp[i][j],dp[i-1][j - arr[i-1].goodsPrice] +  arr[i-1].goodsValue) 
            }
//             过滤得到附件的数组
            let sub = arr.filter((item)=>item.goodsParent!=0).filter((item)=>item.goodsParent==arr[i-1].goodsCode);
//          //如果有附件 则取j元 - 当前主件价格 - 当前附件价格 所对应的最大值 +  当前主件最大值 + 当前附件最大值
//             条件为小于j元 j代表0-goodsTotal对应的价格
//             dp[i][j] 代表第i件物品对应j元能得到的最大值
            if(sub.length == 1){
                if(j>=arr[i-1].goodsPrice + sub[0].goodsPrice){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - arr[i-1].goodsPrice - sub[0].goodsPrice] +  arr[i-1].goodsValue + sub[0].goodsValue) 
                }
            }
            if(sub.length == 2){
                if(j>=arr[i-1].goodsPrice + sub[0].goodsPrice){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - arr[i-1].goodsPrice - sub[0].goodsPrice] +  arr[i-1].goodsValue + sub[0].goodsValue) 
                }
                if(j>=arr[i-1].goodsPrice + sub[1].goodsPrice){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - arr[i-1].goodsPrice - sub[1].goodsPrice] +  arr[i-1].goodsValue + sub[1].goodsValue) 
                }
                 if(j>=arr[i-1].goodsPrice + sub[0].goodsPrice + sub[1].goodsPrice){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - arr[i-1].goodsPrice -  sub[0].goodsPrice - sub[1].goodsPrice] +  arr[i-1].goodsValue + sub[0].goodsValue+ sub[1].goodsValue) 
                }
            }
        }
    }
     console.log(dp[goodsCount][goodsTotal])
}
getRes(newArr,goodsCount,goodsTotal / base)