#include?
#include?
#include?

using?namespace::std;

/*
?*?foodCount:?the?total?number?of?food
?*?total:?the?rest?of?money
?*?price:?price?array?of?each?food
?*?value:?nutrition?value?of?each?food
?*?result:?result[i][j]?represents?the?maximum?nutrition?value?with?buying?the?i?foods
*/
vector?maxNutritionValue（int?foodCount?int?total?vector?&price?vector?&value?vector>?&result）
{
????for?（int?i?=?1;?i?<=?foodCount;?++i）
????{
????????for?（int?j?=?1;?j?<=?total;?++j）
????????{
????????????if?（price[i]?>?j）???????????//?can?not?pay?the?ith?food
????????????????result[i][j]?=?result[i?-?1][j];
????????????else
????????????{
????????????????//?two?state?represent?the?（i-1）th?round
????????????????int?value1?=?result[i?-?1][j?-?price[i]]?+?value[i];
????????????????int?value2?=?result[i?-?1][j];

????????????????//?the?ith?state?can?only?change?from?the?two?（i-1）th?state
????????????????if?（value1?>?value2）
????????????????????result[i][j]?=?value1;
????????????????else
????????????????????result[i][j]?=?value2;
????????????}
????????}
????}

????vector?plan（foodCount?0）;

????//?get?the?chosen?of?foods?if?plan[i]?=?1?the?ith?food?has?been?chosen?otherwise?plan[i]?=?0
????for（int?i?=?foodCount;?i?>?0;?--i）
????{
????????if（result[i][total]?>?result[i?-?1][total]）
????????{
????????????plan[i?-?1]?=?1;?????//?buy?the?food
????????????total?-=?price[i];
????????}
????????else