算法整理 复习：背包九讲

本文主要是介绍算法整理 复习：背包九讲，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、01 背包

01背包问题

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN 1005int n, m;
int bag[MAXN];
int val[MAXN], wight[MAXN];int main(void)
{cin >> n >> m;for (int i=1;i<=n;i++){cin >> wight[i] >> val[i];}for (int i=1;i<=n;i++){for (int j=m;j>=wight[i];j--){bag[j] = max(bag[j], bag[j-wight[i]] + val[i]);}}cout << bag[m] << endl;return 0;
}

---

二、完全背包

完全背包问题

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN 1005int n, v;
int val[MAXN], wight[MAXN], f[MAXN];int main(void)
{cin >> n >> v;for (int i=1;i<=n;i++){cin >> wight[i] >> val[i];}for (int i=1;i<=n;i++){for (int j=wight[i];j<=v;j++){f[j] = max(f[j], f[j-wight[i]]+val[i]);}}cout << f[v];return 0;
}

---

三、多重背包

3.1 普通多重背包

多重背包题 I

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN 105int n, v;
int val[MAXN], wight[MAXN], num[MAXN], f[MAXN];int main(void)
{cin >> n >> v;for (int i=1;i<=n;i++){cin >> wight[i] >> val[i] >> num[i];}for (int i=1;i<=n;i++){for (int j=v;j>=wight[i];j--){for (int k=1;k<=num[i] && j>=k*wight[i];k++){f[j] = max(f[j], f[j-k*wight[i]] + k*val[i]);}}}cout << f[v];return 0;
}

3.2 二进制优化多重背包

多重背包问题 II

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN 25000int n, v, cnt;
int val[MAXN], wight[MAXN], f[MAXN];int main(void)
{cin >> n >> v;for (int i=1;i<=n;i++){int w, vlu, m;cin >> w >> vlu >> m;for (int k=1;k<m;k*=2){m -= k;wight[++cnt] = k * w;val[cnt] = k * vlu;}if (m > 0){wight[++cnt] = m * w;val[cnt] = m * vlu;}}for (int i=1;i<=cnt;i++){for (int j=v;j>=wight[i];j--){f[j] = max(f[j], f[j-wight[i]]+val[i]);}}cout << f[v];
}

3.3 单调队列优化多重背包

多重背包问题 III

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN 20005int n, V;
int wight[MAXN], val[MAXN], num[MAXN], f[MAXN];struct{int pos,value;
}que[MAXN];int main(void)
{cin >> n >> V;for (int i=1;i<=n;i++){cin >> wight[i] >> val[i] >> num[i];num[i] = min(num[i], V/wight[i]);for (int j=0;j<wight[i];j++){int head = 0;int rear = -1;for (int k=0;k<=(V-j)/wight[i];k++){int x = f[k * wight[i] + j] - k * val[i];while (head <= rear && que[head].pos < k - num[i]){head++;}while (head <= rear && que[rear].value <= x){rear--;}que[++rear].pos = k;que[rear].value = x;f[k * wight[i] + j] = que[head].value + k * val[i];}}}cout << f[V];return 0;
}

---

这篇关于算法整理 复习：背包九讲的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---