0-1背包问题

题目描述:

给定 N 件物品和一个容量为 H 的背包。每件物品有一个价值 V[i] 和一个重量 W[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最?

输入格式：

• 第一行包含两个整数 N 和 H，分别表示物品的数量和背包的容量。
• 第二行包含 N 个整数，分别表示每件物品的价值 V[i]。
• 第三行包含 N 个整数，分别表示每件物品的重量 W[i]。
• 输出格式：
• 输出一个整数，表示在不超过背包容量的情况下，能够装入背包的最大物品总价值。

样例输入:

4 8

3 4 5 6

2 3 4 5

样例输出：

10 

 我们采用动态规划的思路来解决。

我们根据这里的样例列一个表：物品种类为4，背包容量为8。

根据它的输入列一个表格：01背包

题目的意思就可以理解为容量为8的背包，放入那几件商品，价值最大？

1.定义一个dp数组dp[i][j]；表示前i件物品，放入j容量背包的最大价值。

我们可以列一个表格

 2.求状态转移方程：

对一个物品，我们有两种选择：

   1.放入背包：dp[i][j] = max(dp[i - 1][j], V[i - 1] + dp[i - 1][j - W[i - 1]]);即前 i-1 个物品在容量为 j - W[i-1] 的背包中能够获得的最大价值加上第 i 个物品的价值 V[i-1]（因为是从下标0开始的所以是i-1）

   2.不放入背包：dp[i][j] = dp[i-1][j]；即前 i-1 个物品在容量为 j 的背包中能够获得的最大价值

综合这两种选择，状态转移方程为：dp[i][j]=max(dp[i−1][j],V[i−1]+dp[i−1][j−W[i−1]]) 

需要注意的是，只有当 j >= W[i-1] 时，才能选择将第 i 个物品放入背包

3.初始化它的边界：dp[0][0] =0；即没有物品时，也没有空间，所以价值为0；

                                dp[0][j]=0;    即没有物品，有容量，它的价值依然为0；

                                 dp[i][0] ;      即有物品，没有背包容量 ，它的价值依然为0；

举个例子我们这里求dp[1][2];表示前1件商品，放入j容量背包的最大价值，由于它的重量为2<=背包容量。假如不放它进背包，那么当前容量就等于前i-1件最大价值，即为0，如果放入最大价值为3,取最大的即选3；

代码如下: 

int N, H;
int V[1001], W[1001];
int dp[1001][1001];

int main()
{
    cin >> N >> H;
    // 输入每个商品的价值
    for (int i = 0; i < N; i++)
    {
        cin >> V[i];
    }
    // 输入每个商品的重量
    for (int i = 0; i < N; i++)
    {
        cin >> W[i];
    }

    // 1. 定义 dp[i][j] 表示前 i 个商品，放入容量为 j 的背包的最大价值
    // 2. 初始化边界
    for (int i = 0; i <= N; i++)
    {
        dp[i][0] = 0; // 容量为 0 时，价值为 0
    }
    for (int j = 0; j <= H; j++)
    {
        dp[0][j] = 0; // 没有商品时，价值为 0
    }

    // 3. 状态转移
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= H; j++)
        {
            if (j >= W[i - 1]) // 确保当前容量 j 大于等于当前商品的重量 W[i-1]
            {
                dp[i][j] = max(dp[i - 1][j], V[i - 1] + dp[i - 1][j - W[i - 1]]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j]; // 如果当前容量不足以放入第 i 个商品，则继承上一次的最大价值
            }
        }
    }

    cout << dp[N][H] << endl; // 输出最大价值
    return 0;
}