完全背包问题

~~这是蒟蒻的第一篇文章，写的不好，有错误请指出~~

题目

题目描述

有

n

种物品，放在容积为

m

的背包里，每种物品都有无限个。对于第

i(1 \le i \le n)

个物品有对应的体积

w_i

和价值

v_i

。请你选择一种取法，使得背包里物品的价值最大。

输入格式

第一行两个整数

n,m

表示物品的个数和背包的容积

接下来的

n

行每行两个整数

w_i

和

v_i

表示第

i

个物品的体积和价值

输出格式

一个整数，表示背包内的最大价值

输入样例

CPP

输出样例

CPP

暴力做法

状态描述：

dp_{i, j}

表示前

i (1 \le i \le n)

种物品，放在体积为

j(0 \le j \le m)

的包里，得到的最大价值

转移方程:

可以转化成01背包问题。定义一个数量

k

表示第

i

件物品最多能装的个数。

k

从

0

遍历到

\frac {j} {w_i}

dp_{i,j} = \max_{k=0}^{k \le \frac{j}{w_i}} \{dp_{i-1,j},dp_{i-1,j - k w_i} + k v_i \}

边界：

dp_{0,j}=0

时间复杂度

O(nm^2)

代码：

CPP

#include <iostream>
using namespace std;
 
const int N = 105;
int w[N], v[N];
int dp[N][N];
int n, m;
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i] >> v[i];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            for (int k = 0; k <= j / w[i]; ++k)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
            }
        }
    }
 
    cout << dp[n][m] << endl;
 
    return 0;
}

优化：

思路：

我们可以发现

dp_{i,j}=\max \{dp_{i-1,j},dp_{i-1,j-w_i}+v_i,dp_{i-1,j- 2w_i} +2v_i, \ldots, dp_{i-1,j-kw_i}+k v_i\}

dp_{i,j - w_i} + v_i = \max \left\{ dp_{i-1,j - w_i} + v_i, dp_{i-1,j - 2 w_i} + 2 v_i, dp_{i-1,j - 3 w_i} + 3 v_i, \ldots, dp_{i-1,j - (k+1) w_i} + (k+1) v_i \right\}

dp_{i,j}

的转移方程里除了第一项外，其他都与

dp_{i,j-w_i}+v_i

相等。故有以下式子

转移方程：

dp_{i,j} = \max \{ dp_{i-1,j}, dp_{i,j - w_i} + v_i \}

边界：

dp_{0,j}=0

时间复杂度:

O(nm)

代码：

CPP

#include <iostream>
using namespace std;

const int N = 105;
int v[N], w[N];
int dp[N][N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

完全背包问题

文章操作

完全背包问题

题目

题目描述

输入格式

输出格式

输入样例

输出样例

暴力做法

状态描述：

转移方程:

边界：

时间复杂度

代码：

优化：

思路：

转移方程：

边界：

时间复杂度:

代码：

相关推荐

评论

完全背包问题