多重背包 完全背包 01背包模板

多重背包问题

多重背包问题限定了一种物品的个数，解决多重背包问题，只需要把它转化为0-1背包问题即可。比如，有2件价值为5，重量为2的同一物品，我们就可以分为物品a和物品b，a和b的价值都为5，重量都为2，但我们把它们视作不同的物品。

#include <iostream>
using namespace std;
#define V 1000
int weight[50 + 1];
int value[50 + 1];
int num[20 + 1];
int f[V + 1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, m;
cout << "请输入物品个数:";
cin >> n;
cout << "请分别输入" << n << "个物品的重量、价值和数量:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i] >> num[i];
}
int k = n + 1;
for (int i = 1; i <= n; i++) {
while (num[i] != 1) {
weight[k] = weight[i];
value[k] = value[i];
k++;
num[i]--;
}
}
cout << "请输入背包容量:";
cin >> m;
for (int i = 1; i <= k; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) f[j] = max(f[j], f[j - weight[i]] + value[i]);
}
}
cout << "背包能放的最大价值为:" << f[m] << endl;
}

2.完全背包问题

完全背包问题是指每种物品都有无限件。

#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, m;
cout << "请输入物品个数:";
cin >> n;
cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
cout << "请输入背包容量:";
cin >> m;
for (int i = 1; i <= n; i++) {
for (int j = weight[i]; j <= m; j++) {
f[j] = max(f[j], f[j - weight[i]] + value[i]);
}
}
cout << "背包能放的最大价值为:" << f[m] << endl;
}

1.0-1背包问题

0-1背包问题是指每一种物品都只有一件，可以选择放或者不放

#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int main() {
int n, m;
cout << "请输入物品个数:";
cin >> n;
cout << "请分别输入" << n << "个物品的重量和价值:" << endl;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
cout << "请输入背包容量:";
cin >> m;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) {
f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
}
}
}
cout << "背包能放的最大价值为:" << f[m] << endl;
}

最后

以上就是机灵蜡烛为你收集整理的多重背包 完全背包 01背包模板的全部内容，希望文章能够帮你解决多重背包 完全背包 01背包模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。