问题 G: 【搜索】桐桐的运输方案
时间限制: 1 Sec 内存限制: 64 MB
提交: 46 解决: 14
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
桐桐有N件货物需要运送到目的地，它们的质量和价值分别记为：
质量：W1，W2，…，Wn；
价值：Vl，V2，…，Vn；
已知某辆货车的最大载货量为x，并且当天只能运送一趟货物。这辆货车应该运送哪些货物，才能在不超载的前提下使运送的价值最大？
输入
第1行是一个实数，表示货车的最大载货量x(1<x≤I00)。
第2行是一个正整数，表示待运送的货物数n(1<n≤20)。
后面n行每行两个用空格隔开的实数，分别表示第1至第n件货物的质量w和价值V。
输出
第1行为被运送货物的总价值（只输出整数部分）；
第2行为按编号大小顺序输出所有被运送货物的编号（当一件都不能运送时，不输）。
样例输入
20
4
3.5 4
4 5
5 6.8
6.9 7
样例输出
22
1 2 3 4
#include<bits/stdc++.h> #include<queue> #include<iostream> using namespace std; double cap,w[30],val[30],maxn; int n,o; int main() { cin >> cap >> n; for (int i = 1; i <= n; i++)cin >> w[i] >> val[i]; for (int i = 0; i < (1 << n); i++) { double curw=0,curv = 0; for (int j = 0; j < n; j++) { if ((1 << j)&i) { curw += w[j + 1], curv += val[j + 1]; } if (curw > cap)break; } if (curw > cap)continue; if (maxn < curv)maxn = curv, o = i; } maxn = floor(maxn); cout << maxn << endl; for (int i = 0; i < n; i++) { if ((1 << i)&o)cout << i+1 << ' '; } }
原文链接: https://www.cnblogs.com/czy-power/p/10356527.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/289719
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
