01背包问题

avatar
作者
筋斗云
阅读量:0

动态规划思路

  1. 定义状态

    • dp[i][j] 表示前 i 个物品恰放入一个容量为 j 的背包可以获得的最大价值。
  2. 状态转移方程

    • 如果不放第 i 个物品,那么 dp[i][j] = dp[i-1][j]
    • 如果放第 i 个物品,且 j >= W[i],那么 dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i])
  3. 初始化

    • 当没有任何物品可选择时,即 i = 0,所有 dp[0][j] = 0
    • 当背包容量为 0 时,即 j = 0,所有 dp[i][0] = 0
  4. 最终结果

    • dp[N][totalWeight] 即为所求的最大价值。

#include <iostream> #include <vector> #include <algorithm>  using namespace std;  int main() {     int totalWeight,N;     cin>>totalWeight>>N;      vector<int> value(N+1);     vector<int> weight(N+1);     for (int i = 1; i <=N; i++)     {         cin>>weight[i]>>value[i];     }      vector<vector<int>> dp(N+1,vector<int>(totalWeight+1, 0));     for(int i=0;i<=N;i++)     {         for (int j = 1; j <= totalWeight; j++)         {             if(j<weight[i])//说明装不下             {                 dp[i][j]=dp[i-1][j];             }             else{//能装下,但是也要考虑,装?不装,对应的情况             dp[i][j]=max(dp[i-1][j - weight[i]] + value[i],dp[i-1][j]);             //dp[i-1][j - weight[i]] + value[i]对应装的 情况             //dp[i-1][j]对应不装的 情况             }         }              }     cout<<dp[N][totalWeight]<<endl;         return 0; } 

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!