0-1背包问题理解

问题内容：有i种类型的物品，它们的重量和价值分别是weight[i]和value[i]，每种物品数量只有一个。现在，有一个容量为j的背包，如何装取物品，使得背包价值最大？

解题思路：典型的动态规划问题。

1.确定dp数组含义：dp【i】【j】任取【0~i】的物品放进背包的容量为j时，其最大价值为dp【i】【j】。

2.递推公式：不放物品i时的背包价值——dp【i】【j】=dp【i-1】【j】;放物品i时的背包价值——dp【i】【j】=max( dp【i-1】【j】,dp【i-1】【j-weight[i]】+value[i])

 #include
 #include
 using namepase std;
 ?
 void bag01(vector<int>& weight,vetor<int>& value, int backweight)
 {
     //定义dp数组
     vector<vector<int>> dp(weight.size(),vector<int>(backweight+1,0));
     //初始化
     for(int j=weight;j<=backweight;j++)
     {
         dp[0][j]=value[0];
     }
     for(int i=1;i<weight.size();i++)//遍历物品
     {
         for(int j=0;j<=backweight;j++)//遍历背包容量
         {
             if(j<weight[i]) dp[i][j]=dp[i-1][j];//背包容量小于物品i的容量,即不放物品i
             else
             {
                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value); //放物品i
             }
             
         }
     }
     cout<<dp[weight.size()-1][backweight]<<endl;
 }
 int main()
 {
     vector<int> weight;//物品重量
     cin>>weight;
     vector<int> value;//物品价值
     cin>>value;
     int backweight;//背包容量
     while(cin>>backweight)
     {
         bag01(weight,value,backweight);
     }
     return 0;
 }

TRANSLATE with

Bing Webmaster Portal