题目链接 https://www.luogu.com.cn/problem/P1064
题解:
对每种主件的 附件的集合 进行一次 01 背包处理, 就可以先求出 对于每一种主件包括其附件的组合中, 每种花费的最大价值, 对应不同的方案.
在对主件进行背包处理.
需要注意的是在对每个主件的附件进行处理时, 要恰好花完价钱, 否则方案数会非常多.
- Code:
- #include <bits/stdc++.h>
- # define LL long long
- using namespace std;
- const int maxn=65;
- int N, m;
- struct Obj{
- int v,p,q;
- }arr[maxn];;
- Obj fujian[maxn][5]; // 主件的附件信息
- int fcnt[maxn]; // 主件的附件个数
- int f[33000]; //i 价钱取得的最大价值
- int V[maxn][5]; // 主件的不同方案需要的价钱
- int P[maxn][5]; // 主件的不同方案获得的价值
- int pcnt[maxn]; // 各个主件的方案数
- int main(){
- scanf("%d %d", &N, &m);
- int a,b,c;
- for(int i=1;i<=m;++i){
- scanf("%d %d %d", &a, &b, &c);
- arr[i].v=a;
- arr[i].p=b;
- arr[i].q=c;
- if(c>0){
- fcnt[c]++;
- fujian[c][fcnt[c]].v=a;
- fujian[c][fcnt[c]].p=b;
- fujian[c][fcnt[c]].q=c;
- }
- }
- for(int i=1;i<=m;++i){ // 处理主件及其相应附件
- if(arr[i].q==0){
- // 只取主件
- ++pcnt[i];
- V[i][pcnt[i]]=arr[i].v;
- P[i][pcnt[i]]=arr[i].v*arr[i].p;
- // 考虑取不同附件
- memset(f,-1,sizeof(f));
- f[0]=0;
- for(int j=1;j<=fcnt[i];++j){
- for(int k=N-arr[i].v;k>=fujian[i][j].v;--k){
- if(f[k-fujian[i][j].v]!=-1)
- f[k]=max(f[k],f[k-fujian[i][j].v]+fujian[i][j].v*fujian[i][j].p);
- }
- }
- for(int j=0;j<=N-arr[i].v;++j){ // 不同价钱对应的价值, 即不同的方案
- if(f[j]!=-1){
- ++pcnt[i];
- V[i][pcnt[i]]=arr[i].v+j;
- P[i][pcnt[i]]=arr[i].v*arr[i].p+f[j];
- }
- }
- }
- }
- memset(f,0,sizeof(f));
- for(int i=1;i<=m;++i){
- if(arr[i].q==0){
- for(int j=N;j>=arr[i].v;--j){
- for(int k=1;k<=pcnt[i];++k){
- if(j>=V[i][k]){
- f[j]=max(f[j],f[j-V[i][k]]+P[i][k]);
- }
- }
- }
- }
- }
- printf("%d", f[N]);
- return 0;
- }
注意到题目说只有三种情况, 每个主件可以有 0 个, 1 个或 2 个附件.
所以可以这样写:
- #include <bits/stdc++.h>
- # define LL long long
- using namespace std;
- const int maxn=65;
- int N, m;
- struct Obj{
- int v,p,q;
- }arr[maxn];;
- Obj fujian[maxn][5]; // 主件的附件信息
- int fcnt[maxn]; // 主件的附件个数
- int f[33000]; //i 价钱取得的最大价值
- int V[maxn][5]; // 主件的不同方案需要的价钱
- int P[maxn][5]; // 主件的不同方案获得的价值
- int pcnt[maxn]; // 各个主件的方案数
- int main(){
- scanf("%d %d", &N, &m);
- int a,b,c;
- for(int i=1;i<=m;++i){
- scanf("%d %d %d", &a, &b, &c);
- arr[i].v=a;
- arr[i].p=b;
- arr[i].q=c;
- if(c>0){
- fcnt[c]++;
- fujian[c][fcnt[c]].v=a;
- fujian[c][fcnt[c]].p=b;
- fujian[c][fcnt[c]].q=c;
- }
- }
- for(int i=1;i<=m;++i){
- if(arr[i].q==0){
- for(int j=N;j>=arr[i].v;--j){
- f[j]=max(f[j],f[j-arr[i].v]+arr[i].v*arr[i].p);
- if(fcnt[i]>0 && j-arr[i].v-fujian[i][1].v>=0){
- f[j]=max(f[j],f[j-arr[i].v-fujian[i][1].v]+arr[i].v*arr[i].p+fujian[i][1].v*fujian[i][1].p);
- }
- if(fcnt[i]>1 && j-arr[i].v-fujian[i][2].v>=0){
- f[j]=max(f[j],f[j-arr[i].v-fujian[i][2].v]+arr[i].v*arr[i].p+fujian[i][2].v*fujian[i][2].p);
- if(j-arr[i].v-fujian[i][2].v-fujian[i][1].v>=0){
- f[j]=max(f[j],f[j-arr[i].v-fujian[i][2].v-fujian[i][1].v]+arr[i].v*arr[i].p+fujian[i][2].v*fujian[i][2].p
- +fujian[i][1].v*fujian[i][1].p);
- }
- }
- }
- }
- }
- printf("%d", f[N]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3402778.html