给定背包容量W=20，以及6个物品。重量分别为（5，3，2，10，4，2），价值分别为（11，5，15，18，12，6），求解此背包问题。
//Ex8_2 #include<iostream> #include<vector> using namespace std; int W = 20; vector<pair<int, int>> bags = { {5,11},{3,8},{2,15},{10,18},{4,12},{2,6} }; int visited[100]; struct Result{ vector<int> bags; int cost; }tmp,max; void print(Result &re) { for (int& i : re.bags) cout << bags[i].first<<"("<<bags[i].second<<")" << " "; cout << "价值：" << re.cost << endl; } void dfs(int w) { if (w >= 0) { cout << "可选方案："; print(tmp); if (max.bags.empty() || tmp.cost > max.cost) max = tmp; } for (int i = 0; i < bags.size(); i++) { if (!visited[i] && bags[i].first <= w) { visited[i] = 1; tmp.bags.push_back(i); tmp.cost += bags[i].second; dfs(w - bags[i].first); tmp.cost -= bags[i].second; tmp.bags.pop_back(); visited[i] = 0; } } } int main() { dfs(W); cout << "最优方案："; print(max); return 0; }
