Time Limit: 1 second
Memory Limit: 128 MB

【問(wèn)題描述】

潛水員為了潛水要使用特殊的裝備。他有一個(gè)帶2種氣體的氣缸：一個(gè)為氧氣，一個(gè)為氮?dú)狻Ｗ対撍畣T下潛的深度需要各種的數(shù)量

的氧和氮。潛水員有一定數(shù)量的氣缸。每個(gè)氣缸都有重量和氣體容量。潛水員為了完成他的工作需要特定數(shù)量的氧和氮。他完

成工作所需氣缸的總重的最低限度的是多少？

例如：潛水員有5個(gè)氣缸。每行三個(gè)數(shù)字為：氧，氮的（升）量和氣缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潛水員需要5升的氧和60升的氮?jiǎng)t總重最小為249（1，2或者4，5號(hào)氣缸）。

你的任務(wù)就是計(jì)算潛水員為了完成他的工作需要的氣缸的重量的最低值。

【輸入格式】

第一行有2整數(shù)m，n（1<=m<=21，1<=n<=79）。它們表示氧，氮各自需要的量。
第二行為整數(shù)k（1<=n<=1000）表示氣缸的個(gè)數(shù)。
此后的k行，每行包括ai，bi，ci（1<=ai<=21，1<=bi<=79，1<=ci<=800）3整數(shù)。這些各自是：第i個(gè)氣缸里的氧和氮的容量及
汽缸重量。

【輸出格式】

僅一行包含一個(gè)整數(shù)，為潛水員完成工作所需的氣缸的重量總和的最低值。

Sample Input

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

Sample Output

249

【題解】
對(duì)于每一個(gè)氣缸。都有選或不選兩種可能。也即0/1背包。但是這次不再是所用的花費(fèi)不大于X的問(wèn)題了。
而應(yīng)該是剛好為X，或者到達(dá)了要求之后，大于等于X的問(wèn)題。比如你要5單位的氧氣。你不能說(shuō)含有不超過(guò)
5單位氧氣的最大花費(fèi)，而應(yīng)該說(shuō)恰為5單位，或者給6單位也可以。大于5就直接讓他等于5就可以了。
然后因?yàn)槭?/1背包。更新的話要逆序更新。
這種恰好問(wèn)題。要置其他f[i][j](二維費(fèi)用)為一個(gè)很大的數(shù)，然后f[0][0] =0 ，表示0氧氣，0氮?dú)猓?/p>
不需要?dú)飧住Ｋ灾亓繛?；從f[0][0]開(kāi)始得到其他值。
【代碼】
#include <cstdio>

int mo2,mn2,n,wo2[1010],wn2[1010],weight[1010],f[100][100];

void input_data()
{
	scanf("%d%d",&mo2,&mn2);
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
		scanf("%d%d%d",&wo2[i],&wn2[i],&weight[i]);
}

void get_ans()
{
	for (int i = 0;i <=mo2;i++)
		for (int j = 0;j <= mn2;j++)
			f[i][j] = 2100000000 / 3; //把其他f[i][j]置為一個(gè)很大的值 
	f[0][0] = 0; //0氧氣0氮?dú)獾闹亓繛? 
	for (int i = 1;i <= n;i++)	
		for (int j = mo2 + wo2[i];j >= wo2[i];j--) //因?yàn)榇笥谒璧闹狄彩欠弦蟮?
			for (int k = mn2 + wn2[i];k >= wn2[i];k--)
				{
					int mm = j;
					if (j > mo2) //如果j是大于所需值，就讓他為所需值就好 
						mm = mo2;
					int nn = k;
					if (k > mn2)
						nn = mn2;
					if (f[mm][nn] > f[j-wo2[i]][k-wn2[i]] + weight[i]) //嘗試更新解。 
						f[mm][nn] = f[j-wo2[i]][k-wn2[i]] + weight[i];	
				}
}

void output_ans()
{
	printf("%d",f[mo2][mn2]); //最后輸出f[mo2][mn2]表示達(dá)到所需值，所花費(fèi)的最少重量 
}	

int main()
{
	//freopen("F:\rush.txt","r",stdin);
	input_data();
	get_ans();
	output_ans();
	return 0;
}




                            
總結(jié)
                            

                                以上是生活随笔為你收集整理的【9929】潜水员的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
                            
                            

                                如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。