背包问题

有N件物品和一个容量为W 的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

如何思考这一类动态规划问题呢？我的思路是想清楚问题的条件与最终目的。这道题的最终目的是 max(value)，其中有两个限制条件，物品的总重，物品集合(物品是有限的集合 {1,2,..,n}每个物品只能选择一个)。

我们先想想如何暴力的解决？如果是暴力的解决，就是穷举所有的组合:

int max_val = 0
int W = w
int items_len = n
int find_max(start_item,current_weight,current_val){
    if (start_item == items_len-1){
        if current_weight + w[start_item] < W {
            current_val += v[start_item]
            max_val = max(max_val,current_val)
        }
       return 0;
    }
    for i = start_item..(items_len-2){
        if current_weight + w[i] < W {
            find_max(i+1,current_weight + w[i],current_val+v[i])
        }
        else{
            find_max(i+1,current_weight ,current_val)
        }
    }
}

这是一个深度优先的搜索算法。

那有没有更好的解决办法呢？

接下来该如何思考呢？我们尝试看看能不能将问题分解为更小的问题(这是解决计算机问题的思路)。那么该如何分解呢？

假设i 是我们选择的最后一个物品，我们将问题分解为之问题求 OPT[i] = 在物品 0..i 的子集中使得val `最大的组合。

case1: 如果不选择i 我们将在 {1..i-1} 中找最优，即OPT[i] = OPT[i-1]

case2: 如果我们选择 i 我们如何将问题再往下分解呢？似乎没有思路了。

直觉的思考是如果有一个背包 weight = W - w[i]，那么如果他有一个 opt[i-1][weight]的最优解即在 weight的限制条件下，在 {1..i-1}中找到一个最优的组合。这两种情况就能很好的描述了。

case1: 如果不选择i我们将在 {1..i-1} 中找最优，并且重量的限制为W，即 OPT[i][W] = OPT[i-1][W]

case2: 如果我们选择 i 则 OPT[i][W] = OPT[i-1][W-w[i]] + v[i]

OPT[i][w] = max{OPT[i-1][W-w[i]] + v[i], OPT[i-1][W]}

总结来说 dp 的思路就是思考限制条件，与问题的分解。

int knapsack(vector<int>&w,vector<int>&v,int W){
    vector<vector<int>>dp(w.size()+1,vector<int>(W+1,0));
    for(int i =1 ; i<=  v.size();i++){
        for(int j = 1 ; j <= W;j++){
            if(j < w[i-1]){
                dp[i][j] = dp[i-1][j];
            }
            else{
                 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
            }
        }
    }
    return dp[v.size()][W];
}

完全背包问题

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

由于这里没有物品数量的限制，所以：

OPT[w] = max{[OPT[w-w[i]]+v[i] for i in len]}