©2020-2024 ioDraw All rights reserved,
Privacy Policy
#include<iostream> #include<string> using namespace std; int Pow(const int& base
,const int& n) { int result = 1; for (int i = 0; i < n; i++) { result *= base; }
return result; } string getString(int i) { string result; while (i != 0) { char
c= i % 2 +'0'; result += c; i = i / 2; } result.reserve(); return result; } int
GetMaxValue(int* weights, int* values, const int& n,const int& weight) { int
maxValue= 0; for (int i = 0; i < Pow(2, n); i++) { int tempValue = 0; int
tempWeight= 0; string str = getString(i); for (int i = 0; i < str.length(); i++)
{ if (str[i] == '1') { tempValue += values[i+n-str.length()]; tempWeight +=
weights[i + n - str.length() ]; } } if (tempWeight <= weight) { if (maxValue <
tempValue) { maxValue = tempValue; } } } return maxValue; } int main(void) { int
n; cout << "请输入物品的数量："; cin >> n; int maxWeight; cout << "请输入包的最大承重："; cin >>
maxWeight; int* weights = new int[n]; int* values = new int[n]; cout <<
"请输入每件物品的重量："; for (int i = 0; i < n; i++) { cin >> weights[i]; } cout <<
"请输入每件物品的价值："; for (int i = 0; i < n; i++) { cin >> values[i]; } int maxValue =
GetMaxValue(weights, values, n, maxWeight); cout << "最大价值是：" << maxValue << endl
; return 0; }