今天开始再度研究算法问题，就从动态规划开始吧。
行李打包问题就是在固定的容积内放入价值不同的产品，能够使包装满后价值最大，接近生活点就是吃自助，价钱一定的前提下使自己受益最大。
int n,capacity;
int volume[100],need[100];
int cache[1001][1001]
int pack(int capacity,int item)
{
if(item == n)
{
return 0;
}
int &ret =cache[capacity][item];
if (ret != -1)
{
return ret;
}
ret=pack(capacity,item+1);
if(capacity >=volume[item])
{
ret= max(ret,pack(capacity- capacity[item],item+1)+need[item];
}
return ret;
}
void reconstruct(int capacity,int item, vector<string> &picked)
{
if(item == n)
{
return;
}
if(pack(capacity,item) == pack(capacity,item+1))
{
reconstruct(capacity,item+1,picked);
}
else
{
picked.push_back(name[item]);
reconstruct(capacity-volume[item],item+1,picked);
}
}
