题目描述阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100) 堆金币第 i 堆金币的总重量和总价值分别是 mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 T(T≤1000) 的背包但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割分割完的金币重量价值比也就是单位价格不变。请问阿里巴巴最多可以拿走多少价值的金币输入格式第一行两个整数 N,T。接下来 N 行每行两个整数 mi,vi。输出格式一个实数表示答案输出两位小数。输入输出样例输入 #1复制4 50 10 60 20 100 25 100 15 45输出 #1复制240.00题解#include iostreamusing namespace std;#include algorithm#include iomanipstruct charge{int weight;int fee;double value;//引入value代表其每份金币的具体价值实际上就是总价除重量得出单价的意思请读者自行体会};bool compare(charge p1,charge p2){if(p1.value!p2.value) return p1.valuep2.value;return p1.feep2.fee;}int main(){int n,t;cinnt;struct charge c[105];for(int i0;in;i){cinc[i].weightc[i].fee;c[i].value(double)c[i].fee/c[i].weight;}sort(c,cn,compare);double sum0;for(int i0;in;i){if(tc[i].weight){sumc[i].fee;t-c[i].weight;}else{sumt*c[i].value;break;}}coutfixedsetprecision(2)sumendl;system(pause);return 0;}
洛谷：P2240 【深基12.例1】部分背包问题
发布时间：2026/7/24 8:19:25
题目描述阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100) 堆金币第 i 堆金币的总重量和总价值分别是 mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 T(T≤1000) 的背包但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割分割完的金币重量价值比也就是单位价格不变。请问阿里巴巴最多可以拿走多少价值的金币输入格式第一行两个整数 N,T。接下来 N 行每行两个整数 mi,vi。输出格式一个实数表示答案输出两位小数。输入输出样例输入 #1复制4 50 10 60 20 100 25 100 15 45输出 #1复制240.00题解#include iostreamusing namespace std;#include algorithm#include iomanipstruct charge{int weight;int fee;double value;//引入value代表其每份金币的具体价值实际上就是总价除重量得出单价的意思请读者自行体会};bool compare(charge p1,charge p2){if(p1.value!p2.value) return p1.valuep2.value;return p1.feep2.fee;}int main(){int n,t;cinnt;struct charge c[105];for(int i0;in;i){cinc[i].weightc[i].fee;c[i].value(double)c[i].fee/c[i].weight;}sort(c,cn,compare);double sum0;for(int i0;in;i){if(tc[i].weight){sumc[i].fee;t-c[i].weight;}else{sumt*c[i].value;break;}}coutfixedsetprecision(2)sumendl;system(pause);return 0;}
)
