完全背包问题

题目描述

设有 n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 M，今从 n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

输入

第一行：两个整数，M(背包容量，M ≤ 200)和N(物品数量，N ≤ 30)；

第2−N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

样例

10 4
2 1
3 3
4 5
7 9

max=12

公式

f[i][j] =max(f[i - 1][j], f[i][j - v[i]] + w[i]);

二维数组代码

#include<bits/stdc++.h>
using namespace std;

int f[1010][1010], v[1010], w[1010],n, m;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j <= m; j ++ )
        {
            if(v[i] <= j)
                f[i][j] =max(f[i - 1][j], f[i][j - v[i]] + w[i]);
            else
                f[i][j] = f[i - 1][j];
        }
    }
    cout << "max=" << f[n][m] << endl;
}