一、背包问题(knapsack problem)
http://en.wikipedia.org/wiki/Knapsack_problem）
1. 0-1 背包问题（0-1 knapsack problem the most common problem）：
2. 有界背包问题（bounded knapsack problem BKP）：
3. 无界背包问题（unbounded knapsack problem UKP）：
二、0-1背包问题
特点：每件物品或被带走，或被留下（需要做出0-1选择）。不能只带走某个物品的一部分或带走两次以上同一个物品。
输入：数组v，数组w，可取走的物品数n，可取走的最大重量W。
输出（可选）：数组x，x中每个元素为1或0，1对应该物品被取走，0对应不取；满足条件下背包的总重量及总价值。
分析：一个物品选或不选，共有2^n中组合方式，目的就是找到这些组合方式中满足条件的一种。
解法一 暴力破解法
分析：枚举2^n种组合方式下的总重量和总价格，找到满足条件的最优解。
时间复杂度：O(lg1 + lg2 + lg3 + ... + lg(2^n)) = O(lg((2^n)!)) > O(2^n)。
算法C实现：
枚举时采用位运算，在每一位上通过判断0或1指示该位表示的物品是否取走。
void knapsack_problem_violent(ElementType* v, ElementType* w,
CommonType count,
ElementType maximum_weight,
ElementType* best_weight,
ElementType* best_value,
ElementType* x)
{
assert(v != NULL && w != NULL && count >= 1 && maximum_weight > 0 &&
x != NULL && best_value != NULL && best_weight != NULL);
/// initialize
CommonType i, j, k;
ElementType temp_weight, temp_value;
CommonType x_temp[MAX_COUNT] = {0};
*best_weight = 0; *best_value = 0;
memset(x, 0, count * sizeof(ElementType));
/// detect all combination
CommonType type_count = pow(2, count);
for (i = 0; i < type_count; i++) {
/// get current total weight and totoal value and combination
memset(x_temp, 0, count * sizeof(ElementType));
temp_value = 0;
temp_weight = 0;
k = 0;
j = i;
do {
/// 1 bit correspond to 1 item
if (j & 0x1) {
temp_value += v[k];
temp_weight += w[k];
x_temp[k] = 1;
}
k++;
} while (j >>= 1);
/// save best state: best weight, best value and item state
if (temp_weight < maximum_weight && temp_value > *best_value) {
*best_weight = temp_weight;
*best_value = temp_value;
memcpy(x, x_temp, count * sizeof(ElementType));
}
}
}
解法二 递归算法 分治策略
递归的子问题定义详见解法三，这里只给出算法C实现：
ElementType knapsack_problem(ElementType* v, ElementType* w,
CommonType count,
ElementType maximum_weight)
{
assert(v != NULL && w != NULL && count >= -1 && maximum_weight >= 0);
/// no items or no weight
if (count == -1 || maximum_weight == 0)
return 0;
/// the i-th item's weight exceed the range
if (w[count - 1] > maximum_weight)
return knapsack_problem(v, w, count - 1, maximum_weight);
/// get best solution
ElementType a = knapsack_problem(v, w, count - 1, maximum_weight);
ElementType b = knapsack_problem(v, w, count - 1,
maximum_weight - w[count - 1]) + v[count - 1];
return a > b ? a : b;
}
解法三 动态规划 dynamic programming
动态规划分析：
最优子结构 Optimal Structure：即满足一个问题的最优解包含子问题最优解的情况。选择一个给定物品i，则需要比较选择i的形成的子问题的最优解与不选择i的形成的子问题的最优解。问题分成两个子问题，进行选择比较，选择最优的一种。
重叠子问题 Overlapping subproblems：子问题之间并非独立，存在重叠情况。
难点：把问题抽象化并建立数学模型，用科学的数学语言描述问题与子问题的关系，找到状态转移点并推出递归关系，以便编程求解。
问题：在N个物品中选择，在背包最大重量W约束下背包所能达到的最大价值。
该问题子问题可分为两个：
子问题1：不选择第N个物品，在前N-1个物品中选择，在背包最大重量W约束下背包所能达到的最大价值可能为问题最优解。
子问题2：选择第N个物品（重量为w，价值为v），并在前N-1个物品中选择，在背包最大重量W-w约束下背包所能达到的最大价值加上第N个物品的价值v可能为问题最优解。
这样问题最优解就可以转化求解相应两种子问题的最优解。数学表达如下：
定义v(i,w)为在前i个物品中选择取舍（并不是说前i个物品都要取），并且背包最大重量为w时背包所能达到的最大价值（最优解）。根据题意可得0<=i<=n，0<=w<=W。
可以得到递归关系：
v(i,w) = max(v(i-1,w),v(i-1,w-wi) + vi) （其中wi,vi为第i个物品重量和价值，v(i-1,w)对应不选择第i个物品时最优解，v(i-1,w-wi)+vi对应选择第i个物品时最优解）
v(i,w) = 0, 此时i = 0 或 w = 0。
v(i,w) = v(i-1,w), 此时wi > w，避免背包最大重量为负数。
时间复杂度：O(n*W)。
算法C实现：
动态规划采用自底向上法（bottom-up method）；
keep数组用于寻找哪些物品被放入背包哪些物品被舍，keep(i,w) = 1表示v(i,w)这一最优解情况下保留第i个物品，keep(i,w) = 0时表示不保留。利用keep数组，可进行回溯（trace back），从而判断v(n,W)情况下哪些物品放入背包，哪些物品被舍去；
V数组和keep数组第一列和第一行分别表示背包最大重量w = 0和可选择物品数为i = 0时问题的解，为特殊解，需要初始化为0（边界问题）。
/**
* @file knapsack_problem_dp_bottom_up.c
* @brief solve 0-1 knapsack problem by dynamic programming
* with bottom-up method.
* @author chenxilinsidney
* @version 1.0
* @date 2015-03-04
*/
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <math.h>
// #define NDEBUG
#include <assert.h>
// #define NDBG_PRINT
#include "debug_print.h"
typedef int ElementType; ///< element data type
typedef int CommonType; ///< common data type
/// data
#define MAX_COUNT 100 ///< count of the items
#define MAX_WEIGHT 300 ///< max weight of the items for memory
ElementType v[MAX_COUNT + 1] = {0};
ElementType w[MAX_COUNT + 1] = {0};
CommonType x[MAX_COUNT + 1] = {0};
CommonType V[MAX_COUNT + 1][MAX_WEIGHT + 1] = {{0}};
CommonType keep[MAX_COUNT + 1][MAX_WEIGHT + 1] = {{0}};
ElementType knapsack_problem(ElementType* v, ElementType* w,
ElementType* x,
CommonType count,
ElementType maximum_weight,
ElementType V[MAX_COUNT + 1][MAX_WEIGHT + 1],
ElementType keep[MAX_COUNT + 1][MAX_WEIGHT + 1])
{
assert(v != NULL && w != NULL && count >= -1 && maximum_weight >= 0 &&
V != NULL);
CommonType i, j;
/// initialize first row
for (i = 0; i <= maximum_weight; i++) {
V[0][i] = 0;
keep[0][i] = 0;
}
for (i = 1; i <= count; i++) {
/// initialize first column
V[i][0] = 0;
keep[i][0] = 0;
/// get matrix solution
for (j = 1; j <= maximum_weight; j++) {
if(w[i - 1] <= j) {
ElementType a = V[i - 1][j];
ElementType b = V[i - 1][j - w[i - 1]] + v[i - 1];
V[i][j] = a > b ? a : b;
if (a > b)
keep[i][j] = 0;
else
keep[i][j] = 1;
} else {
V[i][j] = V[i - 1][j];
keep[i][j] = 0;
}
}
}
/// display the matrix
printf("-V--");
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", j);
printf("\n");
for (i = 0; i <= count; i++) {
printf("%3d ", i);
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", V[i][j]);
printf("\n");
}
printf("keep");
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", j);
printf("\n");
for (i = 0; i <= count; i++) {
printf("%3d ", i);
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", keep[i][j]);
printf("\n");
}
/// get and display the item list by keep matrix
printf("k = ");
ElementType K = maximum_weight;
for (i = count; i >= 1; i--) {
if (keep[i][K] == 1) {
printf("%3d ", i);
K -= w[i - 1];
x[i - 1] = 1;
} else {
x[i - 1] = 0;
}
}
printf("\n");
printf("actual weight = %3d\n", maximum_weight - K);
return V[count][maximum_weight];
}
int main(void) {
/// read data to array
/// read maximum weight
ElementType maximum_weight = 0;
if (scanf("%d\n", &maximum_weight) != 1 || maximum_weight <= 0) {
DEBUG_PRINT_STATE;
DEBUG_PRINT_STRING("can not get right maximum_weight");
}
CommonType count = 0;
while(count < MAX_COUNT && scanf("(%u,%u)\n", v + count, w + count) == 2) {
++count;
}
/// get result
ElementType best_value = knapsack_problem(v, w, x, count,
maximum_weight, V, keep);
/// output result
printf("best value = %d\n", best_value);
CommonType i;
for (i = 0; i < count; i++) {
printf("item index = %3d, value = %3d, weight = %3d, get_flag = %3d\n",
i + 1, v[i], w[i], x[i]);
}
return EXIT_SUCCESS;
}
输入数据：
10 (10,5) (40,4) (30,6) (50,3)
输出数据：
-V-- 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 10 10 10 10 10 10 2 0 0 0 0 40 40 40 40 40 50 50 3 0 0 0 0 40 40 40 40 40 50 70 4 0 0 0 50 50 50 50 90 90 90 90 keep 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 2 0 0 0 0 1 1 1 1 1 1 1 3 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 1 1 1 1 1 1 1 1 k = 4 2 actual weight = 7 best value = 90 item index = 1, value = 10, weight = 5, get_flag = 0 item index = 2, value = 40, weight = 4, get_flag = 1 item index = 3, value = 30, weight = 6, get_flag = 0 item index = 4, value = 50, weight = 3, get_flag = 1
优化：
1.内存空间优化（减少空间复杂度），把v从二维数组v(i,w)降为一维数组v(w)，理由：子问题只需要一维方向上的信息，考虑到更新一维数组是否对后续问题求解带来影响，采用递减方式进行以防止旧有数据被更新而无法使用；
2.可选优化（未实现）：可以在遍历过程中随着i增加而读入相应物品的数据vi和wi，避免开辟两个长度数组存储这些物品数据。
优化部分代码：
ElementType knapsack_problem(ElementType* v, ElementType* w,
ElementType* x,
CommonType count,
ElementType maximum_weight,
ElementType V[MAX_COUNT + 1],
ElementType keep[MAX_COUNT + 1][MAX_WEIGHT + 1])
{
assert(v != NULL && w != NULL && count >= -1 && maximum_weight >= 0 &&
V != NULL);
CommonType i, j;
/// initialize first row
for (i = 0; i <= maximum_weight; i++) {
keep[0][i] = 0;
}
for (i = 1; i <= count; i++) {
/// initialize first column
V[0] = 0;
keep[i][0] = 0;
/// get matrix solution
for (j = maximum_weight; j >= 1; j--) {
if(w[i - 1] <= j) {
ElementType b = V[j - w[i - 1]] + v[i - 1];
if (V[j] < b) V[j] = b;
if (V[j] > b)
keep[i][j] = 0;
else
keep[i][j] = 1;
} else {
keep[i][j] = 0;
}
}
}
/// display the matrix
printf("-V--");
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", j);
printf("\n");
for (i = 0; i <= count; i++) {
printf("%3d ", i);
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", V[j]);
printf("\n");
}
printf("keep");
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", j);
printf("\n");
for (i = 0; i <= count; i++) {
printf("%3d ", i);
for (j = 0; j <= maximum_weight; j++)
printf("%3d ", keep[i][j]);
printf("\n");
}
/// get and display the item list by keep matrix
printf("remain weight = ");
ElementType remain_weight = maximum_weight;
for (i = count; i >= 1; i--) {
if (keep[i][remain_weight] == 1) {
printf("%3d ", i);
remain_weight -= w[i - 1];
x[i - 1] = 1;
} else {
x[i - 1] = 0;
}
}
printf("\n");
printf("actual weight = %3d\n", maximum_weight - remain_weight);
return V[maximum_weight];
}
其他：采用动态规划解决0-1背包问题，贪心算法对0-1背包问题无效。
三、分数背包问题（factional knapsack problem）：
与0-1背包问题区别：可以那种物体的一部分，而不是只能做出二元（0-1）选择。
使用贪心算法（greedy algorithm），我们计算每个物品单位重量价值，遵循贪心策略，首先尽量多地拿走物品单位重量价值最高的物品，以此类推，直到达到上限W。
时间复杂度：由于需要进行对物品的单位重量价值进行排序，时间复杂度为O(nlgn)。
贪心算法（greedy algorithm）：
最优子结构：对一个问题来说，如果他的最优解包含子问题的最优解，那该问题就就具有最优子结构性质。
贪心选择性质：一个全局最优解可以通过局部最优（贪心）选择来得到。
注意：贪心算法和动态规划对比。（详见《算法导论》）