背包问题之0-1背包

背包问题是典型的动态规划例子。我们可将子问题的解存储下来，以免计算其母问题时需用到子问题结果而重复计算。

问题阐述

给定背包容量W，n个物品及各个物品的价值和重量，问如何选择使背包能装下物品的价值最大？

定义数据结构

• 背包容量W
• 物品个数n
• 各个物品价值和重量分别为v[n], w[n]
• (动态规划数组)dp[n][W]，dp[i][j]表示当背包容量达到j时，前i个物品所具有的最佳价值组和

状态转移方程

对第i个物品的判断，有两种可能性：

• 该物品重量大于当前背包容量，则dp[i][j] = dp[i-1][j]

• 该物品重量小于当前背包容量时，并不是无脑加入，而需要判断加入该物品后背包容量剩余j-w[j]时的价值是否会比不加入物品i大
  那么可写出如下状态转移方程：

  
  状态转移方程

考虑下面这个问题

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>


using namespace std;
const int maxn = 105;
int v[maxn], w[maxn], dp[maxn];

int main()
{
    int n; cin >> n;
    int W; cin >> W;
    memset(v, 0, sizeof(v));
    memset(w, 0, sizeof(w));
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; i++)
        cin >> w[i] >> v[i];
    for(int i=1; i<=n; i++){
        int ww = W;
        for(; ww>=w[i]; ww--){ //注意是从大到小的顺序
            dp[ww] = max(dp[ww], dp[ww-w[i]]+v[i]);  //递推公式
        }
    }
    cout << dp[W];
    return 0;
}

Tips

• 背包的每个剩余容量均对应一个物品最优价值
• 按背包容量的降序动态规划