思路

明显是DP

题目看似有些复杂,实际上只有5种情况:

1. 选主件
2. 选主件+附件1
3. 选主件+附件2
4. 选主件+附件1+附件2

状态转移方程为:

\(f[m]=max(f[m],f[m−v[i]]+w[i],f[m−v[i]−v[j]]+w[i]+w[j],f[m−v[i]−v[k]]+w[i]+w[k],f[m−v[i]−v[j]−v[k]]+w[i]+w[j]+w[k])\)

代码实现就不难了

代码

#include <bits/stdc++.h>
using namespace std;

int itemw[100][3],itemv[100][3],mainw[100],mainv[100],f[32005];

int main(){
    int v,n;
    cin>>v>>n;
    for (int i=1;i<=n;++i){
        int t1,t2,t3;
        scanf("%d %d %d",&t1,&t2,&t3);
        if (!t3){
            mainw[i]=t1;
            mainv[i]=t1*t2;
        }else{
            itemw[t3][0]++;
            itemw[t3][itemw[t3][0]]=t1;
            itemv[t3][itemw[t3][0]]=t1*t2;  //小心别写错
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=v;j>=mainw[i]&&mainw[i]>0;--j){
            f[j]=max(f[j],f[j-mainw[i]]+mainv[i]);
            if (j>=itemw[i][1]+mainw[i]&&itemw[i][0]>=1){
                f[j]=max(f[j],f[j-itemw[i][1]-mainw[i]]+itemv[i][1]+mainv[i]);
            }
            if (j>=itemw[i][2]+mainw[i]&&itemw[i][0]>=2){
                f[j]=max(f[j],f[j-itemw[i][2]-mainw[i]]+itemv[i][2]+mainv[i]);
            }
            if (j>=itemw[i][1]+itemw[i][2]+mainw[i]&&itemw[i][0]>=2){
                f[j]=max(f[j],f[j-itemw[i][1]-itemw[i][2]-mainw[i]]+itemv[i][1]+itemv[i][2]+mainv[i]);
            } //注意判断条件: 主件也要算上
        }
    }
    cout<<f[v];
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/16/