/*本程序旨在利用动态规划解决有价值的0-1背包问题*/
/*物品的大小和价值以及背包的大小保存在一个放置在E盘根目录下的的csv文件中*/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
ifstream in("E://packageProblem.csv");
string line;
string field;
int packageSize;
int objectNum;
getline(in, line);
stringstream ss;
istringstream sin;
ss << line;
ss >> packageSize;
ss.clear();
getline(in, line);
ss << line;
ss >> objectNum;
ss.clear();
int *objectSize = new int[objectNum];
int *objectValue = new int[objectNum];
int sizePointer = 0;
int valuePointer = 0;
while (getline(in, line))
{
cout<<line<<endl;
sin.str(line);
getline(sin, field, ',');
ss << field;
cout<<"size:"<<field<<" ";
ss >> objectSize[sizePointer];
ss.clear();
sizePointer++;
getline(sin, field, ',');
ss << field;
cout<<"value:"<<field<<endl;
ss >> objectValue[valuePointer];
ss.clear();
sin.clear();
valuePointer++;
}
//读入数据的部分结束了
//行是物品件数(0-objectNum),列是背包大小(0-packageSize)
int **table = new int *[objectNum + 1];
for (int i = 0; i < objectNum + 1; i++)
{
table[i] = new int[packageSize + 1];
}
//初始化,第一行和第一列是0
for (int i = 0; i < objectNum + 1; i++)
{
table[i][0] = 0;
}
for (int j = 0; j < packageSize + 1; j++)
{
table[0][j] = 0;
}
//开始写表
for (int i = 1; i < objectNum + 1; i++)
{
for (int j = 1; j < packageSize + 1; j++)
{
if (j < objectSize[i - 1]){
//如果放不下第i件物品,就直接不放
table[i][j] = table[i - 1][j];
//cout<<"table["<<i<<"]["<<j<<"]="<<table[i][j]<<endl;
}
else{
//比较要上之后该物品的值+跳转之后的值和不要该物品的值哪个大
table[i][j] = max(objectValue[i - 1] + table[i-1][j - objectSize[i - 1]], table[i - 1][j]);
//cout<<"table["<<i<<"]["<<j<<"]="<<table[i][j]<<endl;
}
}
}
//表写完了,开始从末尾读表
int i = objectNum;
int j = packageSize;
cout << "总价值为" << table[i][j] << endl;
while (i > 0 && j > 0)
{
if (table[i][j] == table[i - 1][j])
{
cout << "第" << i << "件物品没拿" << endl;
i--;
}
else
{
cout << "第" << i << "件物品拿了" << endl;
j -= objectSize[i-1];
i--;
}
}
while(j==0&&i>0){
cout<<"第" << i << "件物品没拿" << endl;
i--;
}
cout<<endl;
return 0;
}