潜水员：【爆搜 + 二进制枚举 + DP】 |
您所在的位置：网站首页 › 二进制的21是多少 › 潜水员：【爆搜 + 二进制枚举 + DP】 |
|
题目：
潜水员为了潜水要使用特殊的装备。 他有一个带2种气体的气缸：一个为氧气，一个为氮气。 让潜水员下潜的深度需要各种数量的氧和氮。 潜水员有一定数量的气缸。 每个气缸都有重量和气体容量。 潜水员为了完成他的工作需要特定数量的氧和氮。 他完成工作所需气缸的总重的最低限度的是多少？ 例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量： 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。 思路：三种思路！ 暴力搜索： 思路： 递归的出口：枚举的是每一种选法，每种选法都有对应着一定的氧气含量和氮气含量，以及该选法所需要承受的重量。而当氧气含量和氮气含量同时满足需求的时候，即意味着我们可以退出了，无需再选择了！但是我们要比较每种选法下的承受重量以此来枚举出最小重量。由递归的出口可以知道，dfs 的参数应该包含：氧气含量，氮气含量，以及当前重量。但是，我们应该考虑一种情况：当所有气缸都选择了后，如果所选气缸的氧气含量或者是氮气含量不满足要求怎么办，此时会发生无限递归，所以还应该设置一个参数，u：表示第几件物品，如果 u > n后，即为上述的情况！ #include #include #include using namespace std; const int N = 22, M = 80; int oxy[N], dan[M], w[1010]; //第i件气缸的 氧气含量，氮气含量，气缸总重。 int n, m, k; //氧气需要和氮气需要，k个气缸 int ans=1e8; void dfs (int u, int O, int D, int W) { if (O >= n && D >= m) { ans = min(ans, W); return ; } if (u > k) return; dfs (u+1, O, D, W); dfs (u+1, O+oxy[u], D + dan[u], W + w[u]); } int main() { cin >> n >> m >> k; for (int i=1; i > oxy[i] >> dan[i] >> w[i]; dfs (1, 0, 0, 0); cout int sum1=0, sum2=0, weight=0; //累计当前权值总和 for (int j=0; j sum1 += o[j]; sum2 += d[j]; weight += w[j]; } } if (sum1>=m && sum2>=n) { ans = min(ans, weight); } } cout int v1, v2, w; //每个气缸的氧气体积，氮气体积，价值； cin >> v1 >> v2 >> w; for (int j=n; j >= 0; j --) //递推第一维费用. { for (int k=m; k >= 0; k --) //递推第二维费用. { //比较当前物品是放还是不放，哪个使得价值更小，就选哪个选法 f[j][k] = min (f[j][k], f[max(j-v1, 0)][max(k-v2, 0)] + w); } } } cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |