01背包 核心：状态转移方程。 问题简述： 有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 在01背包问题中，每个物品只有一个，每个物品只需要考虑选与不选两种情况，所以可以使用回溯法搜索出所有情况，时间复杂度为O（2^n），n表示物品的数量，如果不选择将其放入背包内，则无需处理，如果选择放入背包内，由于不清楚之前放入物品占了多大空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
暴力的解法是指数级别的时间复杂度，进而才需要动态规划的解法来进行优化！ 状态转移方程： dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]) ，dp[i][j] 第i个物品，放进容量为j的背包，价值总和最大是多少。 最主要的就是对dp进行初始化， 首先将 dp 第0行和第0列初始化为0 ，表示不放物体时最大价值为0 （物体编号从1开始）。 for(int i=1;i<=N;i++) {     for(int j=1;j<=M;j++)     {         if(j>w[i-1])             dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);         else             dp[i][j]=dp[i-1][j];     } } 这是最原始的01背包，具体问题还得具体分析。 可以发现，每次只是使用上一行的数据来计算下一行， 所以可以用一维数组来记录上一行的值，但使用一维的时候要逆序，如果不逆顺序，数组前面的值会覆盖后面的值，重复计算。 for(int i=1;i<=N;i++) {     for(int j=W;j>=0;j--)     {         if(j>w[i-1])             dp[j]=max(dp[j], dp[j - w[i-1]]+v[i-1];      } }   例子： 物品 A重4kg 价值300，B重3kg价值200，C重1kg价值150，背包总重4kg，求最多能装的价值。   #include <iostream> using namespace std; int dp[3][4]; int main() {     int w[3]={4,3,1};     int v[3]={300,200,150};     for (int i=1;i<=3;i++)         {             for (int j=1;j<=4;j++)             {                 if (j>=w[i-1])                     dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);                 else                     dp[i][j]=dp[i-1][j];             }         }     int ans=dp[3][4];     cout<<ans<<endl;     return 0; }     #include <iostream> using namespace std; int dp[1000][1000]; int main() {     int N,M;     cin>>N>>M;     int array[N];     for(int i=0; i<N; i++) cin>>array[i];     dp[0][0]=1;     dp[0][array[0]/2]=1;     dp[0][array[0]]=1;     for(int i=1; i<N; i++)     {         for(int j=0; j<M; j++)         {             if(j>=array[i])                 dp[i][j]=(dp[i-1][j]+dp[i-1][j-array[i]]+dp[i-1][j-array[i]/2])%(int)(1e9+7);             else if(j>=array[i]/2)                 dp[i][j]=(dp[i-1][j]+dp[i-1][j-array[i]/2])%(int)(1e9+7);             else                 dp[i][j]=dp[i-1][j];             if(i==N-1)             {                 if(i<M-1)                     cout<<dp[i][j]<< ' ';                 else                     cout<<dp[i][j]<<endl;             }         }     }     return 0; }   注： 最关键的就是初始化和确定遍历顺序。 初始化定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。 遍历顺序可以先物品后背包，也可以先背包后物品，但前者理解起来更简单一些。