标签归档:DP

动态规划-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;
}