动态规划-完全背包问题

Description

有 n 个重量和价值分别为 wi, vi 的物品。从这些物品中挑选出总重量不超过 W 的物品,求所有挑选方案中价值总和的最大值。在这里,每种物品可以挑选任意多件。

Input

第一行为 n 和 W, 1 ≤ n ≤ 100, 1 ≤ W ≤ 10000
之后 n 行每行为 wi, vi, 1 ≤ wi, vi ≤ 100

Output

输出符合题目要求的价值总和的最大值

Sample Input

3 7
3 4
4 5
2 3

Sample Output

10

Hint

01 背包问题与完全背包问题的不同之处在于后者的每件物品可以无限次数选取,因此后者只能递增顺序求解。对于每个物品,我们可以选取 0 件,1 件,…,W/wi 件。对于每个子问题,我们可以转化为“将前 i-1 种物品放入质量为 V 的背包内”,价值为 dp[i - 1][j],“将前 i-1 种物品放入质量为 V - vi*k 的背包内”,价值为 dp[i - 1][j - k * item[i][0]] + k * item[i][1],以及“将前 i-1 种物品放入质量为 V - vi * (k - 1) 的背包内”,价值为 dp[i - 1][j - (k - 1) * item[i][0]] + (k - 1) * item[i][1]

Optimization

空间和时间复杂度优化

因为我们是递增计算,之前所存储的所有结果都是该状态下的最优解,所以我们不需要第三层循环来枚举在当前质量下最合适的当前物品个数。换言之,在考虑“是否放入第 i 件物品”的决策时,需要使用已经放入了第 i 件物品的子状态 dp[i][W - wi]时,只需调用其最优子状态即可。

时间复杂度优化

因为每种物品的个数都是无限的,所以对于 wi > wj 且 vi < vj 的物品 i 可以直接丢弃,整体复杂度约 O(n^2)。

题解

#include <cstdio>
inline int max(int a, int b)
{
    return a > b ? a : b;
}
int dp[10010], n, w;
int main()
{   
    scanf("%d%d", &n, &w);
    int item[n+1][2];
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &item[i][0], &item[i][1]);
        for (int j = 1; j < i; j++)
        {
            if (item[i][0] > item[j][0] && item[i][1] < item[j][1])
            {
                n--;
                i--;
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = item[i][0]; j <= w; j++)
        {
            if (j < item[i][0])
                dp[j] = dp[j-1];
            else
                dp[j] = max(dp[j], dp[j - item[i][0]] + item[i][1]);
        }
    } 
    printf("%d\n", dp[w]);
    return 0;
}

动态规划-01 背包问题

Description

有 n 个重量和价值分别为 wi, vi 的物品。从这些物品中挑选出总质量不超过 W 的物品,求所有挑选方案中价值总和的最大值。

Input

第一行为 n 和 W, 1 ≤ n ≤ 100, 1 ≤ W ≤ 10000
之后 n 行每行为 wi, vi, 1 ≤ wi, vi ≤ 100

Output

输出符合题目要求的价值总和最大值

Sample Input

4 5
2 3
1 2
3 4
2 2

Sample Output

7

Hint

每个物品只有一件,对于每个物品我们只能选择放或不放。如果不放置,问题转化为“前 i-1 件物品放入质量为 W 的背包内”,价值为 dp[i-1][W]。如果放置,问题则转化为“前 i-1 件物品放入质量为 W-wi 的背包内”,价值为 dp[i-1][W-wi] + vi

Optimization

优化空间复杂度

若将程序从递增计算的方式修改为以 W 递减的方式,这样在计算 dp[v] 的时候 dp[v-vi] 的值就是之前 dp[i-1][V-vi] 的值。从而节省了一个维度的空间。

题解

#include <cstdio>
int n, w, item[110][2], dp[110][10010], t;//item[i][0] weight i, item[i][1] value i
inline int max(int a, int b)
{
    return a > b ? a : b;
}
inline int solve()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j < item[i][0])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i][0]] + item[i][1]);
        }
    }
    printf("%d\n", dp[n][w]);
}
int main()
{
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &item[i][0], &item[i][1]);
    solve();
    return 0;
}