牛客网 华为 机试 HJ16 购物单

题目地址：https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tqId=21239&rp=1&ru=/ta/huawei&qru=/ta/huawei&difficulty=&judgeStatus=&tags=/question-ranking

/*
一看就是背包问题，但是题目中对01背包进行了条件的添加，但主要思路不变，依旧尝试还原为简单的01背包问题。
具体实现思路是将附属物品看作是主物品的一种属性，将特殊的物品之间的关系还原为01背包是解题关键。
由题意可知，一个主物品可以不存在附属物品，或者有一个附属物平，或者有两个，因此可将背包的情况扩充。
主要分为4种情况：
  1、不放入；
  2、放入但不放入主物品的附属；
  3、放入且放入其中一个附属物品（放入哪个就要再分为两种情况考虑）；
  4、放入且放入两个附属物品；
  这样就不需要考虑附属物品与主物品之间的关系，还原成熟悉的01背包问题了。
*/
#include

using namespace std;
//存放物品信息的结构体
struct Thing{
  int price = 0;
  int importance = 0;
  int kind = 0;                 //此物品是主物品还是副物品
  Thing* firstAppendix = NULL;  //此主物品对应的第一个附属物品
  Thing* secondAppendix = NULL; //此主物品对应的第二个附属物品
};

int main(void){
  int money = 0;
  int count = 0;
  cin >> money;
  cin >> count;
  Thing things[count];//先把所有物品的信息存放在things中
  
  for(int i = 0;i < count;i++){
    cin >> things[i].price >> things[i].importance >> things[i].kind;
    things[i].price /= 10;//由于所有价格都是10的倍数因此可以先缩放10倍减少运算开销
  }
  
  vectorint>> bag;//申请背包空间
  vector<int> wide(money / 10 + 1);//背包的“宽度”是依据输入的money所决定的，此基础上再添加一列代表了背包列初始状态
  bag.push_back(wide);//背包行初始状态
  //遍历找到所有附属物品并将其地址写入其主物品的相关属性中（firstAppendix和secondAppendix）
  for(int i = 0;i < count;i++){
    if(things[i].kind != 0){
      if(things[things[i].kind - 1].firstAppendix == NULL){  //注意两个附属物品肯定不重复，要进行条件判断
        things[things[i].kind - 1].firstAppendix = &things[i];
      }else{
        things[things[i].kind - 1].secondAppendix = &things[i];
      }
    }
  }
  
  vector thingsVec;//thingsVec用来存放所有主物品
  
  Thing nullThing;
  thingsVec.push_back(nullThing);//初始化thingsVec时为了后续操作方便，将角标后移，以便于对应背包的角标
  //遍历things将主物品全部放入thingsVec
  for(int i = 0;i < count;i++){
    if(things[i].kind == 0){
      bag.push_back(wide);
      thingsVec.push_back(things[i]);
    }
  }
  //开始背包运算，注意是遍历thingsVec中的所有主物品，已经排除了附属物品
  for(int i = 1;i < bag.size();i++){
    for(int j = 1;j < wide.size();j++){
      //不放的情况
      int notPutIn = bag[i - 1][j];
      //放入但不放入其附属物品
      int putInWithoutAppendix =
        (j - thingsVec[i].price >= 0) ?
          bag[i - 1][j - thingsVec[i].price] + thingsVec[i].price * thingsVec[i].importance
        :0;
      //放入且放入第一个附属物品（对应附属物品存在并且放得下）
      int putInWithFirstAppendix =
        (thingsVec[i].firstAppendix != NULL) ?
          (j - thingsVec[i].price - thingsVec[i].firstAppendix->price >= 0) ?
            bag[i - 1][j - thingsVec[i].price - thingsVec[i].firstAppendix->price] + thingsVec[i].price * thingsVec[i].importance +
            thingsVec[i].firstAppendix->price * thingsVec[i].firstAppendix->importance
          :0
        :0;
      //放入且放入第二个附属物品（对应附属物品存在并且放得下）
      int putInWithSecondAppendix = (thingsVec[i].secondAppendix != NULL) ?
            (j - thingsVec[i].price - thingsVec[i].secondAppendix->price >= 0) ?
              bag[i - 1][j - thingsVec[i].price - thingsVec[i].secondAppendix->price] + thingsVec[i].price * thingsVec[i].importance + 
              thingsVec[i].secondAppendix->price * thingsVec[i].secondAppendix->importance
            :0
          :0;
      //放入且两个附属物品都放入（对应附属物品存在并且放得下）
      int putInWithTwoAppendix = (thingsVec[i].secondAppendix != NULL && thingsVec[i].secondAppendix != NULL) ?
            (j - thingsVec[i].price - thingsVec[i].firstAppendix->price - thingsVec[i].secondAppendix->price >= 0) ?
              bag[i - 1][j - thingsVec[i].price - thingsVec[i].firstAppendix->price - thingsVec[i].secondAppendix->price] + thingsVec[i].price * thingsVec[i].importance +
              thingsVec[i].firstAppendix->price * thingsVec[i].firstAppendix->importance +
              thingsVec[i].secondAppendix->price * thingsVec[i].secondAppendix->importance
            :0
          :0;
      bag[i][j] = max({notPutIn,putInWithoutAppendix,putInWithFirstAppendix,putInWithSecondAppendix,putInWithTwoAppendix});
    }
  }
  cout << (bag[bag.size() - 1][wide.size() - 1]) * 10;//由于之前对价格进行/10操作，因此背包中数据是实际数据的0.1倍，要在最后还原数据就要再乘以10
  return 0;
}