在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。

注意：在本题中，所有的体积值均为整数。

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

//01背包
#include<iostream>
using namespace std;
int main()
{int c,n;	//容量，物品个数int i,j;cin>>c>>n;int *w=new int[n+1];int *v=new int[n+1];for(i=0;i<n;i++)cin>>w[i]>>v[i];int **dp=new int*[n+1];for( i=0;i<=n;i++)dp[i]=new int[n+1];for(i=0;i<=n;i++){dp[0][i]=0;dp[i][0]=0;}for(i=1;i<=n; i++){for(j=0;j<=c;j++){if(j < w[i])  dp[i][j]= dp[i-1][j];else dp[i][j]= max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);}}cout<<dp[i][j];for( i=0;i<n;i++)delete [] dp[i];delete[] dp;return 0;}