poj3624题目解析

题目描述：

给定一个背包，容量为C，有n个物品，第i个物品的重量为Wi，价值为Pi。现在要求在背包容量不超过C的情况下，选择一些物品装入背包，使得装入的物品的总价值最大。输出最大价值。

题目分析：

这是一个经典的背包问题，可以使用动态规划来解决。设f[i][j]表示前i个物品中选择一些装入容量为j的背包的最大价值。则状态转移方程为：

f[i][j] = max(f[i-1][j], f[i-1][j-wi]+pi)

其中，f[i-1][j]表示不选第i个物品，f[i-1][j-wi]+pi表示选第i个物品。取两者的最大值即可。

最终结果为f[n][C]。

代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 3500;
int f[maxn], w[maxn], v[maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= w[i]; j--)
            f[j] = max(f[j], f[j-w[i]]+v[i]);
    printf("%d\n", f[m]);
    return 0;
}

时间复杂度为O(nm)。