有N个物品和一个容量为V的背包，第i件物品的体积为v(i)，价值为w(i)，求将哪些物品装入背包，使得背包中物品的总价值最大。
例题：
输入：
4 6
1 4
2 6
3 12
2 7
输出：
23
分析如下：
#include
using namespace std ;
int main() {
int n , V ; //n件物品，背包容量为V
cin >> n >> V ;
int v[100] , w[100] ; //第i件物品，体积为v[i]，价值为w[i]
for(int i = 1 ; i <= n ; i++)
cin >> v[i] >> w[i] ;
int c[10][100] = {0} ; //c[i][j] 选择第i件物品，背包容量为j时，背包的最大价值
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= v[i] - 1 ; j++) //背包容量小于第i个物品体积时，则不能放入背包
c[i][j] = c[i-1][j] ;
for(int j = v[i] ; j <= V ; j++) //背包容量大于第i个物品体积时，分析放入该物品与不放该物品，哪个使得背包价值最大
c[i][j] = max(c[i-1][j],c[i-1][j-v[i]]+w[i]) ;
}
cout << c[n][V] << endl ; //输出n个物品中，背包容量为V时，背包的最大价值
return 0 ;
}
由于取物品时没有先后顺序，取得当前物品时，背包最大价值只与上一状态有关，所以可以对数组C进行相应处理，以减少空间的使用：
#include
using namespace std ;
int main() {
int n , V ;
cin >> n >> V ;
int v[100] , w[100] ;
int c[2][100] = {0} ;
int t = 0 ;
for(int i = 1 ; i <= n ; i++)
cin >> v[i] >> w[i] ;
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j < v[i] ; j++)
c[t][j] = c[!t][j] ;
for(int j = v[i] ; j <= V ; j++)
c[t][j] = max(c[!t][j],c[!t][j-v[i]]+w[i]) ;
t = !t ;
}
if(n&1)
cout << c[0][V] << endl ;
else
cout << c[1][V] << endl ;
return 0 ;
}
下面这种方法是对上面方法的一种改进，直接倒序比较，相应代码如下：
#include
using namespace std ;
int main() {
int n , V ;
cin >> n >> V ;
int v[100] , w[100] , dp[100] = {0} ;
for(int i = 0 ; i < n ; i++)
cin >> v[i] >> w[i] ;
for(int i = 0 ; i < n ; i++)
for(int j = V ; j >= v[i] ; j--) // 保证能放下该物品
dp[j] = max(dp[j],dp[j-v[i]]+w[i]) ; // 确定的容量下，放该物品与不放该物品,哪个能使背包价值最大
cout << dp[V] << endl ;
return 0 ;
}