//0-1背包问题 #include <iostream> #include <vector> using namespace std; int DP(int maxW, int i, vector<int>& weightVec,vector<int>& valueVec) { if(i == 0) { if(maxW - weightVec[i] > 0) return valueVec[i]; else return 0; } int iOut = DP(maxW, i - 1, weightVec, valueVec); if(maxW - weightVec[i] > 0) { int iIn = DP(maxW - weightVec[i], i - 1, weightVec, valueVec); return iIn + valueVec[i]> iOut ? iIn+ valueVec[i] : iOut; } return iOut; } int main() { int maxW, n, temp; cin>>maxW>>n; vector<int> weightVec, valueVec; for (int i = 0; i < n; ++i) { cin>>temp; weightVec.push_back(temp); } for (int i = 0; i < n; ++i) { cin>>temp; valueVec.push_back(temp); } cout<<(float)DP(maxW, n - 1, weightVec, valueVec)/10.0; return 0; }