本文共 2280 字，大约阅读时间需要 7 分钟。
问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为W（假定物品重量与背包容量值均为整数），应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？设计一个动态规划算法，求解背包问题。
❗算法描述❗：
定义 w[] 存储各物品的重量，v[] 存储各物品的价值，背包的重量为 wsum。
①定义子问题：
k(w, j) = 容量剩余 w 时，从物品 1 到 j 能得到的最高价值。
②是否满足最优子结构：
k(w, j) = max( k(w - wj, j-1) + vj，k(w, j-1))；
前者指，第 j 个物品放入背包中，则产生的最高价值就是，在背包容量为 w-wj 的情况下，在 0 ~ j-1 这些物品中能产生的最高价值 + 第 j 个物品 的价值；
后者指，第 j 个物品不放入背包中，则产生的最高价值就是，背包容量还剩 w，在0 ~ j-1 这些物品中能产生的最高价值。
所以，
| 0, if w == 0 or j = 0k(w, j) = | k(w, j-1), if w < wj | max( k( w - wj, j - 1) + vj, k(w, j-1)), otherwise
③确定解决子问题的次序：
自底向上,bottom - up。
④回溯最优解：
代码如下：
#include#include using namespace std;int max(int, int);void knapsack(vector > k, vector w, vector v, int c, int num);int main(){ int num; cout << "请输入物品个数:" << endl; cin >> num; vector w(num + 1, 0); vector v(num + 1, 0); cout << "请输入各物品的重量:" << endl; for (int i = 1; i < num + 1; ++i) { cin >> w[i]; } cout << "请输入各物品的价值:" << endl; for (int i = 1; i < num + 1; ++i) { cin >> v[i]; } int c; cout << "请输入背包的容量:" << endl; cin >> c; vector > k(c + 1, vector (num + 1)); for (int i = 0; i < c; ++i) { k[i][0] = 0; } for (int j = 0; j < num; ++j) { k[0][j] = 0; } for (int j = 1; j < num + 1; ++j) { for (int i = 0; i < c + 1; ++i) { //如果背包的剩余容量小于第 j 个物品的重量 if (i < w[j]) { k[i][j] = k[i][j - 1]; } //否则 else { k[i][j] = max(k[i - w[j]][j - 1] + v[j], k[i][j - 1]); } } } cout << "背包可能容纳物品的最大价值:" << endl; cout << k[c][num] << endl; knapsack(k, w, v, c, num); cout << endl; return 0;}//回溯结果void knapsack(vector > k, vector w, vector v, int c, int num){ if (c >= w[1] && num > 0) { if (k[c][num] == k[c - w[num]][num - 1] + v[num]) { cout << num << ' '; knapsack(k, w, v, c - w[num], num - 1); } else if (k[c][num] == k[c][num - 1]) { knapsack(k, w, v, c, num - 1); } } else { return; }}int max(int a, int b){ return a > b ? a : b;}
一篇有趣的讲解：
一篇全面的讲解：
转载地址：http://httai.baihongyu.com/