C++ day42背包理论基础01 + 滚动数组

本文介绍: 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weig ht[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！举一个例子：背包最大重量为4，有3个物品，其重量和价值如下表物品为：问背包能背的物品最大价值是多少？1）确定dp 数组以及下标的含义对于

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weig ht[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

举一个例子：背包最大重量为4，有3个物品，其重量和价值如下表

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

int weight_bag(vector<int&gt; weight,vector<int> value,int bagweight){
    vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));
    //初始化.对于物品0
    for(int j=weight[0];j<=bagweight;j++){
        dp[0][j]=value[0];
    }
    //递推（先遍历物品，再遍历背包）
    for(int i=1;i<weight.size();i++){
        for(int j=0;j<=bagweight;j++){
            if(j<weight[i]) dp[i][j]=dp[i-1][j];//如果当前物品重量比背包容量大，则装不下该物品
            //如果当前物品重量比背包容量小，那么可以有两种选择，装下该物品，或是不装该物品
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    return dp[weight.size()-1][bagweight];
}

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

int  weightvalue(int bagweight,vector<int>weight,vector<int>value){
 //初始化dp数组
    vector<int> dp(bagweight+1,0);
    //递推
    for(int i=0;i<weight.size();i++){
        for(int j=bagweight;j>=weight[i];j--){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    return dp[bagweight];
}

class Solution {
public:
    bool canPartition(vector<int>&amp; nums) {
        vector<int> dp(10001,0);//定义dp数组，并将其初始化为0,因为数组中的元素最大是100,且至少有200个数那么最大的重量为200*100=20000，背包中只有一半容量就可以了
        int sum = 0;
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
        }
        if(sum % 2==1) return false;//如果和的一半是奇数，那么不可能有两个子集和相等
        int target = sum/2;
        //递推公式
        //先正序遍历物品，后倒序遍历背包
        for(int i=0;i<nums.size();i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target) return true;
        return false;
    }
};