背包算法—思想与实现

我们先来看一道题

---

问题描述：

有N件物品和一个容积为M的背包。第i件物品的体积为volume[i]，价值为worth[i]。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件，可以选择放或者不放。（N<=3500,M<=13000）

输入格式：

第一行为物品数量N和背包容积M

每行依次输入第i件物品的价值和体积

样例输入：
3 10

3 4

2 6

6 7

样例输出：
6

---

思想:
这道题我们要考虑利益最大化。
下图是蓝色的线条我们的利益

我们只要先找到最大的利益,然后大往小找,可以装进背包就装,不行就继续往小找
要实现此思想需要先把利益的数组排序,然后从下标为0往后找,容量不足时停止。

自定义选择排序

for (int i = 0; i < n; i ++) {for (int j = i; j < n; j ++) {if (bag[j] > bag[i]) {int t = bag[j]; //bag数组代表利益bag[j] = bag[i];bag[i] = t;t = size[j]; //size数组代表背包容量size[j] = size[i];size[i] = t;}}
}

排序后从下标为0往后找

for (int i = 0; i < m; i ++) {if (size[i] <= n) { //如果可以装进背包money += bag[i]; //记录利益n -= size[i]; //装进背包}
}

完整代码:

#include <iostream>
using namespace std;void sort(int bag[],int size[],int n) {for (int i = 0; i < n; i ++) {for (int j = i; j < n; j ++) {if (bag[j] > bag[i]) {int t = bag[j];bag[j] = bag[i];bag[i] = t;t = size[j];size[j] = size[i];size[i] = t;}}}
}int main() {int m,n,money = 0;cin >> m >> n;int bag[m] = {};int size[m] = {};sort(bag,size,m);for (int i = 0; i < m; i ++) {if (size[i] <= n) {money += bag[i];n -= size[i];}}cout << money << endl;return 0;
}