题解 | #购物单#

关键点:

1. 如何转换成背包问题

∵附件不能单独出现,要依赖于主件

∴可以先不看附件,选择主件. 就和0-1背包问题一致

w[i],v[i] 第i个主键的花费,和对应的满意度

2. 设计合适的数据结构

mains[index]主件对应subpart[index]的附件们

mains=[[price1,satis1],...]

subparts=[[[price1,satis1]],...]

w[i][k] 第i个组件的第k种选法

v[i][k] 第i个组件第k种选法对应满意度

//读取数据处理
let [N,m]=readline().split(' ').map(Number);
//处理数据,使主件的输入一定在附件输入之前
let data=[];
for(let i=1;i<=m;i++){
  let [v,p,q]=readline().split(' ').map(Number);
  data.push([i,v,p,q]);
}
data.sort((a,b)=>a[3]-b[3]);

let mains=[],subparts=[];
let map={};  //第i行,对应mains的index
for(let i=0;i<m;i++){
  //处理一条数据
  let [index,v,p,q]=data[i];
  if(q==0){
    //主件
    mains.push([v/10,v/10*p]);
    map[index]=mains.length-1;
  }else {
    //附件
    if(!subparts[map[q]]){
      subparts[map[q]]=[];
    }
    subparts[map[q]].push([v/10,v/10*p]);
  }
}


// 整理数据 w[i][k],v[i][k]
let mLen=mains.length;
let w=new Array(mLen);
let v=new Array(mLen);
for(let i=0;i<mLen;i++){
  w[i]=[];
  v[i]=[];
  //w[i][0]  主件
  //w[i][1]  主件+附件1
  //w[i][2]  主件+附件2
  //w[i][3]  主件+附件1+附件2
  let subpart=subparts[i];
  let subs=subparts[i]?subparts[i].length:0;
  switch(subs){
    case 2:
      w[i][2]=mains[i][0]+subpart[1][0];
      v[i][2]=mains[i][1]+subpart[1][1];
      w[i][3]=mains[i][0]+subpart[0][0]+subpart[1][0];
      v[i][3]=mains[i][1]+subpart[0][1]+subpart[1][1];
    case 1:
      w[i][1]=mains[i][0]+subpart[0][0];
      v[i][1]=mains[i][1]+subpart[0][1];
    case 0:
      w[i][0]=mains[i][0];
      v[i][0]=mains[i][1];
      break; 
  }
}

//背包问题
N=Math.floor(N/10);
let dp=new Array(N+1).fill(0);
//初始化
//i=0 没有买东西,满意度为0.初始化dp数组时已经初始化
for(let j=1;j<=N;j++){
    for(let k=0;k<w[0].length;k++){
      if(j-w[0][k]>=0){
        dp[j]=Math.max(dp[j],v[0][k]);
      }
    }
}
    
//空间优化
for(let i=1;i<mLen;i++){
  for(let j=N;j>0;j--){
    for(let k=0;k<w[i].length;k++){
      if(j-w[i][k]>=0){
        dp[j]=Math.max(dp[j],dp[j-w[i][k]]+v[i][k]);
      }      
    }
  }
}
    
console.log(dp[N]*10);