动态规划 01背包问题滚动数组 C++实现-阿南达文事网

动态规划 01背包问题滚动数组 C++实现

01背包问题

有n中物品，每种只有一个，第i中物品的体积为Vi，重量为Wi，可以选择这些物品放入背包或者不放入背包，是的背包内物品在总体积不超过容量capacity的前提下重量尽量大

算法思想

动态转移方程为d[currentCapacity] = max(d[currentCapacity], d[currentCapacity - items[i].volume] + items[i].weight);，d[currentCapacity]表示将选取的前i个物品装入容量为currenCapacity的背包中的所能达到的最大总重量，d[currentCapacity - items[i].volume] + items[i].weight表示选取前i-1个物品装入容量为currentCapacity- items[i].volume的背包得到的最大重量加上当前物品的重量，其中currentCapacity减去items[i].volume，即减去了当前物品的体积，保证在背包容量能够容纳当前物品的情况下选取，d[currentCapacity - items[i].volume]的值为选取前i-1个物品装入容量为currentCapacity- item[i].volume的背包中最大重量（已经在上一个阶段计算出来），对于每个物品装入不同容量的背包中的情况，从背包最大容量capacity到0，从右往左计算，则在利用动态转移方程计算当前对应d数组值时，d[currentCapacity - items[i].volume]还是上一个状态的值没有改变，若左往右计算则会改变，导致得到意料之外的结果。

int Knapsack::dynamicProgramming() {for (int i = 0; i < d.size(); i++) {d[i] = 0;}for (int i = 0; i < items.size(); i++) {for (int currentCapacity = capacity; currentCapacity >= 0; currentCapacity--) {if (currentCapacity >= items[i].volume) {d[currentCapacity] = max(d[currentCapacity], d[currentCapacity - items[i].volume] + items[i].weight);}}}return d[capacity];
}

样例图解

从右往左计算，计算d数组对应值时，前面的d[currentCapacity - items[i].volume]未被更改可以直接使用，将二维数组降低到一维，利用滚动数组减少内存开销，但只有最后一个状态的值

实现代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Tue Jun 16 11:57:03 2020
*/
#include <bits/stdc++.h>
using namespace std;struct Item {int volume;int weight;
};class Knapsack {
private:vector<int > d;vector<Item> items;int capacity;
public:Knapsack(vector<Item>& items, int capacity);int dynamicProgramming();
};Knapsack::Knapsack(vector<Item>& items, int capacity) {this->items.insert(this->items.begin(), items.begin(), items.end());this->capacity = capacity;d.resize(capacity + 1);
}int Knapsack::dynamicProgramming() {for (int i = 0; i < d.size(); i++) {d[i] = 0;}for (int i = 0; i < items.size(); i++) {for (int currentCapacity = capacity; currentCapacity >= 0; currentCapacity--) {if (currentCapacity >= items[i].volume) {d[currentCapacity] = max(d[currentCapacity], d[currentCapacity - items[i].volume] + items[i].weight);}}}return d[capacity];
}int main(int argc, char const *argv[]) {vector<Item> items;int N, capacity;scanf("%d%d", &N, &capacity);for (int i = 0; i < N; i++) {int volume, weight;scanf("%d%d", &volume, &weight);items.push_back((Item) {volume, weight});}Knapsack *knapsack = new Knapsack(items, capacity);printf("%d", knapsack->dynamicProgramming());return 0;
}

输入数据

输出结果

鸣谢

《算法竞赛入门经典》

最后

由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！