1 問題描述
有n個商品，每個商品的體積是c[j], j = 1, 2, 3, .., n，每個商品的價值是v[j]， j = 1, 2, ..., n.現在有一個背包，體積是c，現在要求往包裡面裝商品，使得在裝得下的情況下，整包商品的價值最大。
2 問題求解的思路
2.1 子問題提取和描述
v[i, c], 當取的商品是{0, 1, 2, 3, ..., i}的子集，最大體積是c時的最大商品總價值。原問題是，當商品是{1,2,3,...,n}的子集，最大體積是c時的商品的最大總價值，這裡縮小了可選擇的商品和容量的可選空間，提取子問題，可見這個子問題和原問題是同構的。
2.2 遞推關系提取
初始值：
v[0, c] = 0
v[i, c] = -∞, c<0，這個時候方案是不存在的。
遞推關系：
分成兩類，選擇i和不選擇i。
不選擇i，商品的最大總價值是v[i-1, c]；
選擇i時，商品的最大總價值是v[i] + v[i-1, c-c[i]]
是以
v[i, c] = max{v[i-1, c], v[i] + v[i-1, c-c[i]]}
2.3 清單求解
例子：c[j] = {3, 5, 2, 7, 4}， v[j] = {2, 4, 1, 6, 5}
v[i, c] c = 0 1 2 3 4 5 6 7 8 9 10
i = 0 0 0 0 0 0 0 0 0 0 0 0
i = 1 0 0 0 2 2 2 2 2 2 2 2
i = 2 0 0 0 2 2 4 4 4 6 6 6
i = 3 0 0 1 2 2 4 4 5 6 6 7
i = 4 0 0 1 2 2 4 4 6 6 7 8
i = 5 0 0 1 2 5 5 6 7 7 9 9
是以，商品的最大價值是9。
3 程式設計實作
#include <iostream>
int max(int a, int b)
{
if (a > b)
{
return a;
} else {
return b;
}
}
int main(int argc, char* argv[])
int capacity[5] = {3, 5, 2, 7, 4};
int value[5] = {2, 4, 1, 6, 5};
int v[6][11] = {0};
for(int i = 1; i < 6; i++)
{
for (int j = 1; j < 11; j++)
{
if ((j - capacity[i]) < 0)
{
v[i][j] = v[i-1][j];
} else {
v[i][j] = max(v[i-1][j], v[i-1][j - capacity[i]] + value[i]);
}
}
}
std::cout<<"the max is:"<<v[5][10]<<std::endl;
}