先看0-1背包问题，背包可承受重量为w,有n个物品，它们的价值和重量分别为vi , costi (i=1~n),问背包最大可以装多少价值的物品。
我们定义一个函数F(w,i)，表示可承受重量为w的背包，对于1~i号物品选择若干个装入背包的最大价值。
那么对于物品i可放或者不可放，因此有
选择不放入i号物品有F( w,i ) = F( w, i-1 )
选择放入i号物品时F(w,i) = F( w-costi , i-1 )+ vi
当然选择放入i号物品的前提条件是i号物品可以放入，即costi<=w
综上有
并且，,有F(0,i)=0(i>=0), F(w,0)=0(w>=0)
在使用循环画表格的时候需要注意：
欲求F(w,i)得知道F(w,i-1), F(w-costi,i-1)，我们将F(w,i)看成二维数组中第w行，第i列，那么即是要先计算w行，i列的上方和左上侧元素
为了求出背包有最大价值时放入的物品，我们从上面的分析知道当F(w,i)=F(w-costi,i-1)+vi时，第i个物品在背包内，因此从表格末位向上搜索即可
所有代码如下：
#include <iostream> #include <algorithm> using namespace std; struct _goods { int cost ; int value ; } ; void knapsack(int w, int n, struct _goods goods[ ] ) { int dp[100][10] ; for (int i = 0; i < 10; ++i) dp[0][i] = 0 ; for (int i = 0; i < 100; ++i) dp[i][0] = 0 ; for (int j = 1; j <= n; ++j)//注意循环的顺序 for (int i = 1; i <= w; ++i) if (i >= goods[j].cost) dp[i][j] = max(dp[i][j - 1], goods[j].value + dp[i - goods[j].cost][j - 1]) ; else dp[i][j] = dp[i][j - 1] ; cout << dp[w][n] << endl ; for (int i = 1; i <= w; ++i) { for (int j = 1; j <= n; ++j) cout << dp[i][j] << " " ; cout << endl ; } int weight = w ; for( int i=n; i>=1; --i ) if (dp[weight][i] == goods[i].value + dp[weight - goods[i].cost][i-1]) { cout << i << " " ; weight = weight - goods[i].cost ; } cout << endl ; } int main( ) { int w, n ; cout << "输入背包可承受重量和物品个数" ; cin >> w >> n ; struct _goods goods[11] ; cout << "输入物品重量和价值" <<endl ; for ( int i=1; i<=n; ++i ){ cin >> goods[i].cost >> goods[i].value; } knapsack(w, n, goods) ; return 0; } 下面再看另一题对于n个不重复的数，我们要从中选出若干个数使他们的和恰好为m，求有多少中选法。
和0-1背包相同，都是选择或者不选择，写出递推表达式即可
对于数据datas[1~n],和m，我们定义F(i,m)表示从datas[1~i]中选择若干个数和为m的方法数。
因此有
如果不选择第i个数有 F( i,m ) = F( i-1,m )
如果第i个数小于等于m，我们选择第i个数有F( i,m )= F( i-1, m-datas[ i ] )
因此当datas[ i ] <=m 有 F( i , m ) = F(i-1,m)+ F( i-1, m-datas[ i ] )
当datas[ i ] > m 有 F( i,m ) = F( i-1 , m )
对于F(i,m)，我们根据以上分析知只需要求出 F(i,m) 的上方及左上方的元素就可以求出F(i,m)
因此我们初始化F(1,x)( x<=m )即可，F(1,datas[1])=1,其余为0，
m-datas[ i ]有可能为0，当m=0的时候定义F(i,0)=1。也可以将datas[i]<=m分为小于和等于两种情况讨论
代码如下：
#include <iostream> using namespace std ; int n,m;//数据个数，需合成数 int _datas[11]; void thesolution( ) { int dp[11][100] ; for ( int i = 1; i <= m; ++i) { if ( _datas[1] == i ) dp[1][i] = 1 ; else dp[1][i] = 0 ; } for (int i = 2; i <= n; ++i) for (int j = 1; j <= m; ++j) if (_datas[i] < j) dp[i][j] = dp[i - 1][j - _datas[i]] + dp[i - 1][j];//包含与不包含 else if (_datas[i] == j) //datas[]中无重复数字 dp[i][j] = 1 + dp[i - 1][j];//包含与不包含 else dp[i][j] = dp[i - 1][ j ] ; cout << dp[n][m] << endl; } int main( ) { cout << "输入数据个数与和"; cin >> n >>m ; cout << "输入数据" << endl; for (int i = 1; i <= n; ++i) cin >> _datas[ i ] ; thesolution( ) ; return 0; } 对于输出所有和为m的集合，我本想着先从F(n,m)到F(1,m)分别向上回溯表格，后来想这样好像不行如果你知道怎么做请告诉我！！
另一个问题，如果给你n个数，取出若干个数求乘积恰好是m要你求出组合数目，以上讨论应该知道了吧。注意余数要为0
0-1背包参考教材《算法设计与分析基础》（Anany Levitin著，第三版）
