题解 | 购物单

#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    
    int jiage[70] = {0};       // 物品价格
    int zhongyao[70] = {0};    // 重要度
    int bianhao[70] = {0};     // 所属主件编号
    int manyi[70] = {0};       // 满意度（价格*重要度）
    int fujian1[70] = {0};     // 主件的第一个附件
    int fujian2[70] = {0};     // 主件的第二个附件
    
    // 读取输入并初始化附件信息
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &jiage[i], &zhongyao[i], &bianhao[i]);
        manyi[i] = jiage[i] * zhongyao[i];
        if (bianhao[i] != 0) {
            // 记录附件到对应的主件下
            if (fujian1[bianhao[i]] == 0) {
                fujian1[bianhao[i]] = i;
            } else {
                fujian2[bianhao[i]] = i;
            }
        }
    }
   int price[70][4]={0};
   int value[70][4]={0};
   int zongshu=0;
 for(int i=1;i<=n;i++)
 {
    if(bianhao[i]!=0)continue;
  
    int count=0;
   
    //只选主件
price[zongshu][count]=jiage[i];
value[zongshu][count]=manyi[i];
//主件加附件1
if(fujian1[i]!=0)
{
price[zongshu][++count]=jiage[i]+jiage[fujian1[i]];
value[zongshu][count]=manyi[i]+manyi[fujian1[i]];
}
if(fujian2[i]!=0)
{
   price[zongshu][++count]=jiage[i]+jiage[fujian2[i]];
value[zongshu][count]=manyi[i]+manyi[fujian2[i]];
}
  if (fujian1[i] != 0 && fujian2[i] != 0) {
  price[zongshu][++count]=jiage[i]+jiage[fujian2[i]]+jiage[fujian1[i]];
value[zongshu][count]=manyi[i]+manyi[fujian2[i]]+manyi[fujian1[i]];
}
  zongshu++;
 }
 int dp[32000]={0};
 for (int i=0;i<zongshu;i++) {
    for(int j=m;j>=0;j--)
    for(int k=0;k<4;k++)
    {
        if(price[i][k]<=j&&price[i][k]!=0)
dp[j]=max(dp[j],dp[j-price[i][k]]+value[i][k]);
    }
 
 }
 printf("%d",dp[m]);
return 0;
}

总感觉也不是动态规划，主要问题在于开始思考错了，将主件加不同附件的组合情况当成单独物品来考虑，导致思路出了问题，后面就是一些无伤大雅的东西了。