Оптимизация пространства для алгоритма динамического программирования рюкзака 0/1 заключается в использовании 1-мерного массива (скажем, А) размера, равного емкости рюкзака, и просто перезаписывать A [w] (если требуется) на каждой итерации i, где A [w] обозначает общее значение, если считаются первые i-ые предметы, а емкость ранца равна w. Если эта оптимизация используется, существует ли способ восстановить список выбранных элементов, возможно, путем сохранения некоторой дополнительной информации на каждой итерации алгоритма DP? Например, в Алгоритме Беллмана Форда можно реализовать аналогичную оптимизацию пространства, и кратчайший путь все еще можно восстановить, если мы сохраним список указателей предшественника, то есть последний прыжок (или, во-первых, в зависимости от того, является ли источник/записывается целевой алгоритм).Реконструкция списка элементов из оптимизированной по пространству реализации ракеты 0/1
Для справки, здесь приведена моя функция C++ для проблемы с рюкзаком 0/1, использующая динамическое программирование, где я создаю вектор 2-d ans, так что ans [i] [j] обозначает общее значение, учитывающее первые i элементы и емкость рюкзака j. Я реконструировать поднято предметов путем обратного обхода этого вектора анс:
void knapsack(vector<int> v,vector<int>w,int cap){
//v[i]=value of item i-1
//w[i]=weight of item i-1, cap=knapsack capacity
//ans[i][j]=total value if considering 1st i items and capacity j
vector <vector<int> > ans(v.size()+1,vector<int>(cap+1));
//value with 0 items is 0
ans[0]=vector<int>(cap+1,0);
//value with 0 capacity is 0
for (uint i=1;i<v.size()+1;i++){
ans[i][0]=0;
}
//dp
for (uint i=1;i<v.size()+1;i++) {
for (int x=1;x<cap+1;x++) {
if (ans[i-1][x]>=ans[i-1][x-w[i-1]]+v[i-1]||x<w[i-1])
ans[i][x]=ans[i-1][x];
else {
ans[i][x]=ans[i-1][x-w[i-1]]+v[i-1];
}
}
}
cout<<"Total value: "<<ans[v.size()][cap]<<endl;
//reconstruction
cout<<"Items to carry: \n";
for (uint i=v.size();i>0;i--) {
for (int x=cap;x>0;x--) {
if (ans[i][x]==ans[i-1][x]) //item i not in knapsack
break;
else if (ans[i][x]==ans[i-1][x-w[i-1]]+v[i-1]) { //item i in knapsack
cap-=w[i-1];
cout<<i<<"("<<v[i-1]<<"), ";
break;
}
}
}
cout<<endl;
}
Я немного смущен в вопросе; вы описываете одномерное пространство состояний 'A', но реализация использует двумерное пространство состояний' ans'? Итак, в основном реализация _space_optimized_ также использует 'ans', но отбрасывает строки для меньших значений' i'? – Codor
@Codor Правильно, я просто показываю, как мы реконструируем список предметов из 2-го вектора. Я не знаю, как мы это сделаем, если это 1-й вектор. Вычисление всего общего значения с помощью этого 1-го вектора является простым, но мы просто должны иметь as [x] вместо ans [i] [x] и продолжать переписывать ans [x]. Если элемент i не включен, команда [x] остается неизменной для итерации, иначе мы заменим ее на ans [i] + v [i-1]. – kabir