Добавление DP в рюкзак 0/1
Вот два разных способа решения задачи о рюкзаке 0/1 с использованием рекурсии.
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vb vector<bool>
long long solve1(int capacity, vi &weight, vi &value, vb &sacked){
long long ans = 0;
int n = weight.size();
for(int i=0; i<n; i++){
if (sacked[i] || weight[i]>capacity) continue;
sacked[i]=true;
ans = max(ans, value[i] + solve1(capacity-weight[i], weight, value, sacked));
sacked[i]=false;
}
return ans;
}
long long solve2(int capacity, vi &weight, vi &value, int idx){
if (idx==-1) return 0;
long long ans = solve2(capacity, weight, value, idx-1);
if (weight[idx]<=capacity) ans = max(ans, value[idx] + solve2(capacity-weight[idx], weight, value, idx-1));
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, c;
cin>>n>>c;
vi w(n), v(n);
for(int i=0; i<n; i++) cin>>w[i]>>v[i];
vb sacked(n, false);
cout<<solve1(c, w, v, sacked)<<'\n';
cout<<solve2(c, w, v, n-1);
}
Я знаю, как добавить dp ко второму методу (в функции solve2). Но я не знаю, как добавить dp к первому методу. Поскольку значения true/false в vector<bool> sacked будут уникальными для каждого вызова, использование dp[capacity][sacked] кажется бесполезным, поскольку одна и та же dp[capacity][sacked] никогда не будет запрошена дважды.
«Я ошибаюсь, заключая, что значение vector<bool> sacked будет уникальным для каждого рекурсивного вызова функции и, следовательно, DP для solve1 невозможен?»
Также никогда не включайте #include<bits/stdc++.h> в свой код, это не стандарт C++.
Речь идет не о добавлении dp в метод. Как вы правильно заметили: значения true/false в векторе <bool> будут уникальными для каждого вызова, использование dp здесь бесполезно. Идея состоит в том, чтобы найти повторно используемые подзадачи и использовать dp, чтобы не повторять одно и то же несколько раз.
@PepijnKramer нет. не в моем контексте. использование #include<bits/stdc++.h> является стандартом соревновательного программирования. мог бы просто ответить на вопрос, не уходя от темы
использование ios_base/tie необходимо, чтобы не получить TLE. так что это был очень бесполезный и обратный совет. «Сначала выучите C++», представьте, что вы говорите студенту университета не экспериментировать с алгоритмами, прежде чем изучать C++ целиком @PepijnKramer
Привычки имеют тенденцию сохраняться, как плохие, так и хорошие. С таким же успехом можно использовать хорошие привычки и закрепить их. Все, что вы узнаете на таких сайтах, — это вредные привычки, плохой код и, зачастую, прямо недействительный код. Если вы представите такой код на собеседовании, вас даже не уволят. Сначала изучите основы, а затем используйте такие сайты для развлечения и развлечения в свободное время.
Почему вы удаляете тег C++? Код написан на C++, поэтому его полезно иметь. В противном случае вы можете получить, например. Специалист по Лиспу читает это и тратит свое время. Если у вас есть тег C++, люди поймут, что речь идет о C++, и нужные люди посмотрят на него. Хотя, рассматривая код, большинство все равно проигнорирует его.
@Someprogrammerdude Я удалил C++, потому что думаю, что скоро появится больше подобных @PepijnKramer. Думаю, я неправильно сформулировал это для энтузиастов ds/алгоритмов. Должно быть: «Я ошибаюсь, заключая, что значение vector<bool> sacked должно быть уникальным для каждого рекурсивного вызова функции и, следовательно, DP для solve1 невозможен?»
@heman bits/stdc++ не имеет НИКАКОГО эффекта во время выполнения... так что вы также можете использовать стандартные методы C++. Проблема в том, что если мне придется нанять «конкурентоспособных программистов», мне придется переквалифицировать их, чтобы они стали инженерами, которые действительно могут писать поддерживаемый код. Спойлерить не буду. В TLE главное — алгоритм (и единственное, что интересует интервьюеров — это то, как вы подходите к проблеме), а не то, что вы можете создать самый быстрый код. То же самое верно и для конкурентного кодирования (речь идет не о написании самого быстрого кода), а о поиске правильного алгоритма.
@heman Я не пытаюсь быть злым, просто показываю вам, что есть совершенно другая сторона C++ и разработки программного обеспечения, которую вы, возможно, пропустили :) И те методы, которые вы считаете само собой разумеющимися, считаются очень плохой практикой в реальной работе разработчика программного обеспечения.
@PepijnKramer та же программа без ios_base/tie DID дает эффект во время выполнения. извините, но слишком много раз случалось, что ios_base/tie необходим даже после написания самого оптимального кода, возможно, это просто нюанс в том, как они обрабатывают ввод/вывод в codeforces. В leetcode это не требуется. Это правда, что конкурентное программирование и инженеры разные, и конкурентное кодирование - это не написание поддерживаемого кода, у меня только что был алгоритмический вопрос с конкурса atcoder.jp/contests/dp/tasks
@PepijnKramer Конкурентное программирование часто требует оптимизации ввода-вывода, поэтому предложение удалить ios_base::sync_with_stdio или cin.tie на самом деле не является улучшением. Дело не только в алгоритме; если бы это было так, конкурсы могли бы включать в себя просто отправку псевдокода. Я тоже предпочитаю не использовать <bits/stdc++.h>, но настоящие конкурсы также требуют быстрого решения задач, поэтому эти включения понятны.
@Unmitigated Я думаю, что это проблема перспектив. Я предполагаю, что форум здесь предназначен для того, чтобы задавать вопросы для улучшения знаний C++. И что сайты конкурентного кодирования имеют собственный форум для конкурентных шаблонов кодирования. (Или, по крайней мере, в SO отсутствует тег конкурентного кодирования), потому что в противном случае кажется, что ответы действительно зависят от точки зрения комментатора.
Ответы 1
Также можно запомнить результаты для solve1. Для любого конкретного выбора k элементов существует k! возможных порядков достижения этого состояния, поэтому одни и те же ответы можно запрашивать несколько раз.
Однако основная проблема этого метода заключается в том, что размер состояния довольно велик, а переход к динамическому программированию также занимает линейное время, что, как правило, слишком неэффективно, чтобы быть практичным.
Обратите внимание, что задачу о рюкзаке 0/1 можно проще и элегантнее решить с помощью табуляции.
#include <span>
#include <vector>
#include <algorithm>
long long solve(int capacity, std::span<int> weights, std::span<int> values) {
std::vector<long long> bestVal(capacity + 1);
for (decltype(values.size()) i = 0; i < values.size(); ++i)
for (int j = capacity; j >= weights[i]; --j)
bestVal[j] = std::max(bestVal[j], bestVal[j - weights[i]] + values[i]);
return bestVal.back();
}
То есть вы имеете в виду, что sacked не будет уникальным для каждого вызова и может использоваться для выявления избыточных подзадач? поэтому я могу запомнить функцию и просто использовать dp[sacked], чтобы получить кешированное значение при повторных вызовах.
@heman Это не всегда будет уникально; вы действительно можете запомнить его, но это все равно будет медленнее, чем другой метод.
Мы проводим обзоры кода не здесь, а здесь: codereview.stackexchange.com. И, пожалуйста, сначала изучите C++. (поэтому ни #defines/no long long, ни ios_base/tie)