背包问题
背包问题是使用dp的经典问题,本篇文章将讲解所有的背包问题,文章也会不断完善,不断通俗易懂。
背包问题是使用dp的经典问题,本篇文章将讲解所有的背包问题,文章也会不断完善,不断通俗易懂。
背包问题是使用dp的经典问题,本篇文章将讲解所有的背包问题,文章也会不断完善,不断通俗易懂。
背包问题是使用dp的经典问题,本篇文章将讲解所有的背包问题,文章也会不断完善,不断通俗易懂。
01背包
Acwing 2. 01背包问题
空间未优化版本
#includeusing namespace std;const int N = 1e3 + 10;int v[N], w[N], f[N][N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ){ scanf("%d%d", &v[i], &w[i]); } for(int i = 1; i <= n; i ++ ){ for(int j = 1; j <= m; j ++ ){ if(j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); } } printf("%d", f[n][m]); return 0;}
空间优化版本
#includeusing namespace std;const int N = 1e3 + 10;int v[N], w[N], f[N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ){ scanf("%d%d", &v[i], &w[i]); } for(int i = 1; i = v[i]; j -- ){ f[j] = max(f[j], f[j - v[i]] + w[i]); } } printf("%d", f[m]); return 0;}
完全背包
Acwing 3. 完全背包问题
空间未优化版本
#includeusing namespace std;const int N = 1e3 + 10;int v[N], w[N], f[N][N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ){ scanf("%d%d", &v[i], &w[i]); } for(int i = 1; i <= n; i ++ ){ for(int j = 1; j <= m; j ++ ){ if(j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]); } } printf("%d", f[n][m]); return 0;}
空间优化版本
#includeusing namespace std;const int N = 1e3 + 10;int v[N], w[N], f[N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ){ scanf("%d%d", &v[i], &w[i]); } for(int i = 1; i <= n; i ++ ){ for(int j = v[i]; j <= m; j ++ ){ f[j] = max(f[j], f[j - v[i]] + w[i]); } } printf("%d", f[m]); return 0;}
多重背包(TODO)
Acwing 多重背包问题 I
#includeusing namespace std;const int N = 1e2 + 10;int v[N], w[N], s[N], f[N][N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ){ scanf("%d%d%d", &v[i], &w[i], &s[i]); } for(int i = 1; i <= n; i ++ ){ for(int j = 1; j <= m; j ++ ){ for(int k = 0; k = k * v[i]; k ++ ){ if(j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); } } } printf("%d", f[n][m]); return 0;}