广东网站建设公司排名,域名138查询网,零基础电商怎么做,做明星同款的网站文章目录题目描述总结解析解法1解法2代码解法3代码题目描述
金明的预算方案 选课 金明今天很开心#xff0c;家里购置的新房就要领钥匙了#xff0c;新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是#xff0c;妈妈昨天对他说#xff1a;“你的房间需要购买哪些物…
文章目录题目描述总结解析解法1解法2代码解法3代码题目描述
金明的预算方案 选课 金明今天很开心家里购置的新房就要领钥匙了新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过 n元钱就行”。今天一早金明就开始做预算了他把想买的物品分为两类主件与附件附件是从属于某个主件的。 如果要买归类为附件的物品必须先买该附件所属的主件。每个主件可以有 0个、1 个或 2 个附件。每个附件对应一个主件附件不再有从属于自己的附件。金明想买的东西很多肯定会超过妈妈限定的 n 元。于是他把每件物品规定了一个重要度分为 5 等用整数1∼5 表示第 5 等最重要。他还从因特网上查到了每件物品的价格都是 10 元的整数倍。他希望在不超过 n 元的前提下使每件物品的价格与重要度的乘积的总和最大。
总结
本题一般性题解是自己独立写的而且思路很简洁复杂度也很好
但是这题WA了好几次每次都是写的时候信心满满交完发现不对用数据检测才发现漏洞老毛病了。。。 以后应该改改这个坏习惯应该先把思路想明白了至少先拿点好的数据测测再交啊
解析
解法1
由于本题的特殊限制对于每个主件最多可以分为五种情况: 1.都不买 2.只买主件 3.买主件与附件A 4.买主件与附件B 5.买主件与附件A、B 然后就可以转化为01背包了
但是我们岂可满足于此
解法2
当附件很多且存在附件之后还有附件时应该怎么办呢 深思熟虑后啊哈 我们把dp开成二维 dp[k][w]表示第k层依赖关系下物品必须购买w的钱获得的最大价值 对于处于第k层的物品A枚举它的所有附件将其作为第k1层递归处理 然后尝试用第k层的dp值更新k-1层的dp值 最后dp[0][n]就是答案 因为每个物品最多处理一次单层递归复杂度是n 所以总时间复杂度为m*n和01背包一样啊有木有 不难看出空间复杂度也是n*m
代码
#include bits/stdc.h
using namespace std;
const int N1e6100;
int n,m;
struct node{int w,v,belong;int nxt[500],nm;
}p[500];
int a,b,c;
int f[80][34050];
int jd[500];
void Try(int k,int id){for(int i0;in;i){if(ip[id].w) f[k][i]-2e9;else f[k][i]f[k-1][i-p[id].w]p[id].v;}for(int i1;ip[id].nm;i){Try(k1,p[id].nxt[i]);}for(int i0;in;i) f[k-1][i]max(f[k-1][i],f[k][i]);
}
void print(){for(int i1;in;i) printf(%d ,f[0][i]);printf(\n);return;
}
int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d%d,p[i].w,p[i].v,p[i].belong);p[i].v*p[i].w;if(p[i].belong) p[p[i].belong].nxt[p[p[i].belong].nm]i;}for(int i1;im;i){if(p[i].belong) continue;Try(1,i);
// print();}printf(%d,f[0][n]);return 0;
}
/*
5 5
1 100 0
2 1 0
1 1000 2
2 2 2
6 10000 0
*/
解法3
树上dfs一边求出size和dfs序注意是后序 因为后序dfs序所以子节点的dfs序比父节点小 这样我们就可以从前往后dp [][]表示前i个点里选j个物品的最大价值 那么转移就是
[][]max([−1][−1][[]],[−[[]]][])
前一个转移是选当前课 后一个是不选当前课那么之前就只能选到−[[]] 最后答案就是dp[n][m]
代码
#include bits/stdc.h
using namespace std;
const int N1800;
int n,m;
/*
op0 被自己覆盖
op1 被儿子覆盖
op2 被父亲覆盖
*/
struct node{int to,nxt;
}p[N];
int fi[N],cnt-1,ru[N];
int v[N],belong[N];
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
int a,b,c;
int pos[N],dfs[N],size[N],tot;
void build(int x,int fa){size[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;build(to,x);size[x]size[to];}dfs[x]tot;pos[tot]x;
}
int dp[N][N];
int main(){memset(fi,-1,sizeof(fi));scanf(%d%d,n,m);for(int i1;in;i){scanf(%d%d,belong[i],v[i]);if(belong[i]) addline(belong[i],i);else addline(0,i);}build(0,-1);for(int i1;itot;i){int idpos[i];for(int jm;j1;j--){dp[i][j]max(dp[i-1][j-1]v[id],dp[i-size[id]][j]);}}printf(%d,dp[n][m]);return 0;
}
/*
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
*/
