题目描述 桐桐有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行为按编号大小顺序输出所有被运送货物的编号（当一件都不能运送时，不输）。
样例输入 Copy 20 4 3.5 4 4 5 5 6.8 6.9 7 样例输出 Copy 22
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int> ans,tmp; double w[N],v[N],W,n,maxn; void dfs(double val,int i,double weight) { if(i>n) //边界 { if(val>maxn) { maxn=val; ans=tmp; } return ; } if(weight+w[i]<=W) { tmp.push_back(i); dfs(val+v[i],i+1,weight+w[i]); //符合条件的 tmp.pop_back(); } dfs(val,i+1,weight); //不符合条件的遍历到下一个 } int main() { cin>>W>>n; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; dfs(0,1,0); cout<<(long long)maxn<<endl; for(int i=0;i<ans.size();i++) cout<<ans[i]<<" "; cout<<endl; }