簡述一下01背包：
背包容量大小固定，有一些物品，每個物品都有重量和價值兩個屬性，且物品唯一不重復（即同一物品只能放入一個），放入物品的總重量不能超過背包容量 ，求放入背包的物品的總價值最大化。0代表不放入，1代表放入。
可以通過建表的方式實現01背包，非遞歸實現。
如果用c[i]表示 i 號物品的重量，v[i]表示 i 號物品的價值，函數f（i，j）表示在有0,1,2...i 號物品和重量限制 j 時能夠得到的最大價值，表result[i][j]=f(i,j)
那麼可以f(i,j)=max((result[i - 1][j - c[i]] + v[i]),(result[i - 1][j]))查表非遞歸。
考慮如下：
有一個物品，我們需要考慮該不該把他放入背包中，無非放入和不放入兩種情況，那麼我們只需要把兩種情況下的總價值都算出來，然後取較大的一個就可以了。
result[i - 1][j - c[i]] + v[i]：放入的情況
總價值為 有 i-1 個物品且重量上限為當前上限 j 減去 i 號物品的重量時的價值 result[i - 1][j - c[i]] 加上 i 號物品的價值 v[i]
result[i - 1][j]：不放入的情況，總價值和 i-1 個物品時一樣（當前考慮的物品是 i 號物品）
代碼部分：
#include<iostream>
#include<string>
using namespace std;
int c[11]; //重量
int v[11]; //價值
int result[11][1001]; //表
///f()函數，計算在i+1個物品和重量上限j的條件下的最大背包價值
int f(int i,int j) //第i個物品，重量上限j //0號物品即第一個物品
{
if (i == 0&&c[i]<=j) //0號物品且重量小於上限
{
return v[i]; //把0號物品放入背包，背包價值為第0號物品的價值
}
if (i == 0 && c[i] > j) //0號物品且重量大於上限
{
return 0; //物品放不進背包，此時背包為空，背包價值為0
}
//不是0號物品的情況
if (i != 0 && j-c[i] >= 0) //i號物品可以放入背包
{
//判斷放入和不放入兩種情況下背包的價值，選擇價值大的方案
return (result[i - 1][j - c[i]] + v[i]) > result[i - 1][j] ? (result[i - 1][j - c[i]] + v[i]) : result[i - 1][j];
} //把這個物品放入背包 //不放入背包
else //i號物品不可以放入背包
return result[i - 1][j];
}
int getResult(int top, int num)
{
if (num == 0) //有0個物品
return 0;
else
{
for (int i = 0; i < num; i++) //第i個物品
{
for (int j = 0; j <= top; j++) //重量
{
result[i][j] = f(i,j); //建表，result[i][j]表示有0,1,2...i個物品和j的重量限制下的最大背包價值
}
}
return result[num-1][top];
}
}
int main()
{
int top; //背包容量
int num; //物品數量
cout << "輸入格式：上限，數量，每個物品的重量和價值。" << endl;
cin >> top;
cin >> num;
for (int i = 0; i < num; i++) //第i個物品的重量和價值
{
cin >> c[i] >> v[i];
}
cout << getResult(top, num) << endl;
return 0;
}
測試樣例1：
測試樣例2：
測試樣例3：
