题目描述
阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 \(N(N \le 100)\) 堆金币,第 \(i\) 堆金币的总重量和总价值分别是 \(m_i,v_i(1\le m_i,v_i \le 100)\)。阿里巴巴有一个承重量为 \(T(T \le 1000)\) 的背包,但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。请问阿里巴巴最多可以拿走多少价值的金币?
输入格式
第一行两个整数 \(N,T\)。
接下来 \(N\) 行,每行两个整数 \(m_i,v_i\)。
输出格式
一个实数表示答案,输出两位小数
样例 #1
样例输入 #1
4 50
10 60
20 100
30 120
15 45
样例输出 #1
240.00
我的作答
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,t;
cin >> n >> t;
int m[110],v[110];
double p[110];
for (int i=0;i<n;i++) {
cin >> m[i] >> v[i];
p[i] = (double) v[i] / m[i];
}
for (int i=0;i<n-1;i++) {
for (int j=0;j<n-i-1;j++) {
if (p[j] < p[j+1]) {
double temp1 = p[j];
p[j] = p[j+1];
p[j+1] = temp1;
int temp2 = m[j];
m[j] = m[j+1];
m[j+1] = temp2;
int temp3 = v[j];
v[j] = v[j+1];
v[j+1] = temp3;
}
}
}
int sum_m=0;
double sum_v=0.00;
for (int i=0;i<n;i++) {
if ((sum_m+m[i])<t) {
sum_v += v[i];
sum_m += m[i];
} else {
sum_v += (double)(t-sum_m) * v[i] / m[i];
sum_m = t;
break;
}
}
printf("%.2lf",sum_v);
return 0;
}
反思总结
首先是一个易错点:
double temp1 = p[j];
p[j] = p[j+1];
p[j+1] = temp1;
冒泡排序时,要注意temp1的数据类型正确;我在做本题时就因为这里导致出错。
然后是背包装满的循环问题:
for (int i=0;i<n;i++) {
if ((sum_m+m[i])<t) {
sum_v += v[i];
sum_m += m[i];
} else {
sum_v += (double)(t-sum_m) * v[i] / m[i];
sum_m = t;
break;
}
}
在装满背包之后,要break跳出循环。(本题不需要)
标签:le,int,样例,深基,数据类型,金币,12,背包 From: https://www.cnblogs.com/xiins/p/18515821