NOI 4.6欲張り1797:金銀島(点数リュック)

テーマの出所:http://noi.openjudge.cn/ch0406/1797/
1797:金銀島
合計時間制限: 3000ms メモリの制限: 65536kB
説明
ある日、KIDは飛行機で金銀島に飛んだ.そこには貴重な金属がたくさんある.KIDはいろいろな宝石の芸術品が好きだが、このような貴重な金属を拒否しない.しかし、彼はポケットを1つしか持っていないので、ポケットはせいぜい重量wのものしか入れられません.島の金属にはs種類があり、それぞれの金属重量が異なり、それぞれn 1,n 2,...,nsであり、同時に各種類の金属の総価値も異なり、それぞれv 1,v 2,...,vsである.KIDは一度にできるだけ多くの金属を持って行きたいと思って、彼に最も多くの金属を持っていくことができることを聞きます.金属は任意に分割することができ、金属の価値はその重量に比例することに留意されたい.
入力
1行目はテストデータのグループ数kであり,後にkグループについて入力する.各試験データは3行を占め、1行目は正の整数w(1<=w<=10000)であり、ポケット荷重の上限を示す.2行目は正の整数s(1<=s<=100)で、金属の種類を表す.3行目にはn 1,v 1,n 2,v 2,...,ns,vsがそれぞれ1種目,2種目,...,s種目の金属の総重量と総価値(1<=ni <=10000, 1 <= vi <=10000).
しゅつりょく
k行、各行出力に対応する入力.出力は小数点以下2桁まで正確にしてください.
サンプル入力

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

サンプル出力

171.93
508.00

 -----------------------------------------------------
構想
点数リュック問題は、欲張り法で、毎回現在の未梱包の単価が最大の貨物梱包を選択し、梱包が満杯になるまで.
コードを実装するときは、小数点以下の桁数の出力を制御することに注意してください.
ヘッダファイル

#include

固定小数位数にfixedを加算する

cout << fixed << setprecision(2) << ans << endl;		//      : 1.23

fixedを付けないのは固定有効桁数です

cout << setprecision(2) << ans << endl;		                //       : 1.2

-----------------------------------------------------
コード#コード#

//   ，    

#include
#include
#include
#include
using namespace std;

struct type {
	double weight, value, price;

	bool operator< (const type &t) const
	{
		return price > t.price;
	}
};

const int NMAX = 105;
type tp[NMAX] = {}; 

int main()
{
#ifndef ONLINE_JUDGE
	ifstream fin ("0406_1797.txt");
	int t,i,n;
	double w,ans,dec;
	fin >> t;
	while (t--)
	{
		ans = 0;
		fin >> w >> n;
		for (i=0; i> tp[i].weight >> tp[i].value;
			tp[i].price = tp[i].value/tp[i].weight;
		}
		sort(tp, tp+n);
		i=0;
		while (w>0)
		{
			dec = min(w, tp[i].weight);
			ans += dec*tp[i].price;
			w -= dec;
			i++;
		}
		cout << fixed << setprecision(2) << ans << endl;		//             
	}
	fin.close();
#endif
#ifdef ONLINE_JUDGE
	int t,i,n;
	double w,ans,dec;
	cin >> t;
	while (t--)
	{
		ans = 0;
		cin >> w >> n;
		for (i=0; i> tp[i].weight >> tp[i].value;
			tp[i].price = tp[i].value/tp[i].weight;
		}
		sort(tp, tp+n);
		i=0;
		while (w>0)
		{
			dec = min(w, tp[i].weight);
			ans += dec*tp[i].price;
			w -= dec;
			i++;
		}
		cout << fixed << setprecision(2) << ans << endl;
	}
#endif
}