UC知道一道NOI模拟题 高分
来源：百度知道 编辑：UC知道 时间：2024/05/10 20:02:43
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
【输入文件】
从文本文件gas.in中读入数据。
第一行有2整数t，a（1<=t<=21，1<=a<=79）。它们表示氧，氮各自需要的量。
第二行为整数n（1<=n<=1000）表示气缸的个数。
此后的n行，每行包括ti，ai，wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。
【输出文件】
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
【输入输出样例】
输入：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出：
249
说一下阶段，状态，决策分别是什么
写下状态转移方程和边界条件
顺便请大牛们留下QQ
以后我有问题还望多指教~
谢谢~
for i1:=1 to n do
for i2:=v1 downto a[i1] do
for i3:=v2 downto b[i1] do
if f[i2-a[i1],i3-b[i1]]+w[i1]<f[i2,i3] then f[i2,i3]:=f[i2-a[i1],i3-b[i1]]+w[i1];
2维的方法：
v1是氧气总量，v2是氮气总量，a,b为各自需要的氧气氮气量。w为重量
以物品为阶段的
开始的时候全付初值maxlongint即可，然后f[0,0]:=0;
我是pascal的不知道合不合品位啊...
建议去做vijos上的
nasa的食物计划
那道题..
没什么自信，不过我来试试看吧。
看了题目之后立刻想到01背包的二维加强版，就是同一个重量有两种价值。
那么建立状态：f[n][i][j],表示前n个气缸（还是气瓶。。反正就是那个背包）在用i氧气和j氮气的情况下的最优重量解
由此得到状态转移方程
f[n][i][j]:=max{f[n-1][i][j]，f[n-1][i-yangqi[n]][j-danqi[n]]+zhongliang[n]}(记不住前面那些数组，直接打拼音了。。。将就将就看吧。。谁叫我是小菜。。。)
那么就是循环体就是
n：1..1000
i：1..21
j：1..79
考虑到时最基本的01背包（就是变二维了）
所以可以简化为二维的f[i][j],再加上最简单的可行性剪枝
循环体就是
n:1..1000
i:21..yangqi[n]
j:79..danqi[n]
即使这样数据规模貌似还是很大，
那么继续做最优化简直
当重量较大而氧气氮气量均较小的那种就可以直接排除不考虑，这个你知道的，很好理解。
然后我就只有这个水平了。。再减我也减不下去了。。谁叫我是小菜啊哈哈。
另外有空建议你去看看背包九讲，好像第五章也不知道第六章就是在说二维背包，有空可以去看看
发测试数据