写一个程序，并在代码中加入中文注释 - The input txt file has 3 lines. The first line has only one integer, the capacity of the bag. The second line has a bunch of positive integers for the value of each item. Two integers are separated by a comma “,”. The third line is in the same format as the second for the weight of each item. - When the calculation is finished, print the optimal value and optimal solution(s) one for each line on the screen. (The optimal value is unique, but the optimal solution may not.) - Sort the items in the optimal solution(s) in the decreasing order of item indices. - The index of items starts from 1. In your program, you need to implement three source files “main.cpp”, “lib.h” and “lib.cpp” For “main.cpp” - It only contains the “main” function. - It reads inputs from .txt files. The input txt file is passed to the main function as an argument. - Each txt file contains exactly one instance. For “lib.h” and “lib.cpp” - .h is the header file for .cpp. - They contain all other functions except “main”.

以下是对应的代码和注释：

// lib.h

#ifndef LIB_H
#define LIB_H

#include <vector>
#include <string>

// 定义物品结构体
struct Item {
int value; // 物品价值
int weight; // 物品重量
int index; // 物品编号
};

// 读取文件并返回相应的参数
void readInput(std::string fileName, int& capacity, std::vector<Item>& items);

// 计算背包问题的最优解
int knapsack(int capacity, std::vector<Item>& items, std::vector<std::vector<int>>& dp);

// 回溯寻找最优解
void backtrack(std::vector<Item>& items, std::vector<std::vector<int>>& dp, std::vector<int>& solution, int i, int j);

// 打印最优解
void printSolution(int optimalValue, std::vector<int>& solution);

#endif

// lib.cpp

#include <iostream>
#include <fstream>
#include <algorithm>
#include "lib.h"

using namespace std;

void readInput(string fileName, int& capacity, vector<Item>& items) {
ifstream inputFile(fileName);
if (inputFile.is_open()) {
// 读取背包容量
inputFile >> capacity;
int value, weight, index = 1;
char comma;
// 读取物品价值和重量
while (inputFile >> value >> comma >> weight) {
items.push_back({value, weight, index});
index++;
}
inputFile.close();
}
}

int knapsack(int capacity, vector<Item>& items, vector<vector<int>>& dp) {
int n = items.size();
// 初始化dp数组，dp[i][j]表示前i个物品放入容量为j的背包中的最大价值
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= capacity; j++) {
dp[0][j] = 0;
}
// 动态规划计算最优解
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (items[i-1].weight > j) {
dp[i][j] = dp[i-1][j];
}
else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i-1].weight] + items[i-1].value);
}
}
}
// 返回最优解
return dp[n][capacity];
}

void backtrack(vector<Item>& items, vector<vector<int>>& dp, vector<int>& solution, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (dp[i][j] == dp[i-1][j]) {
// 第i个物品没有选
backtrack(items, dp, solution, i-1, j);
}
else if (dp[i][j] == dp[i-1][j-items[i-1].weight] + items[i-1].value) {
// 第i个物品选了
solution.push_back(items[i-1].index);
backtrack(items, dp, solution, i-1, j-items[i-1].weight);
}
}

void printSolution(int optimalValue, vector<int>& solution) {
// 打印最优值
cout << "Optimal value: " << optimalValue << endl;
// 打印最优解
cout << "Optimal solution(s):" << endl;
sort(solution.begin(), solution.end(), greater<int>());
for (int i = 0; i < solution.size(); i++) {
cout << solution[i] << " ";
}
cout << endl;
}

// main.cpp

#include <iostream>
#include <vector>
#include "lib.h"

using namespace std;

int main(int argc, char* argv[]) {
if (argc < 2) {
cerr << "Usage: " << argv[0] << " input.txt" << endl;
return 1;
}
string fileName = argv[1];
int capacity;
vector<Item> items;
readInput(fileName, capacity, items);
vector<vector<int>> dp(items.size()+1, vector<int>(capacity+1, 0));
int optimalValue = knapsack(capacity, items, dp);
vector<int> solution;
backtrack(items, dp, solution, items.size(), capacity);
printSolution(optimalValue, solution);
return 0;
}