简单的背包问题

描述
小冯有个存储重量为m的空间存储袋，现在有n件物品，每件物品的重量为w，价值为v。
问小冯最多能装的最大价值为多少？

输入
第一行输入两个数m、n，（1<=n,m<=1000）n表示物品数量，m表示存储袋的最大重量;

接下来的n行，每行输出w,v,(1<=w,v <= 100)分别表示物品的重量，物品的价值;
输出
输出小冯能装的物品最大价值;
样例输入
70 3
71 100
69 1
1 2
样例输出
3

题解
利用动态空间规划
可以建立一个二维数组存储物品价值，行为物品个数，列为重量
比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大
否则返回上一个物品的价值

放入第一个物品重量为1，价值为2

放入第二个物品重量为2，价值为4

代码实例

#include<iostream>
#include<cstdlib>
using namespace std;
int m, n, i, j;
int w[1000], c[1000], f[1000][1000];
int main()
{
    cin >> m >> n;//m代表背包最大能装的重量，n代表物品的数量
    for (i = 1; i <= n; i++) {
        cin >> w[i] >> c[i];//输入每个物品的重量和价值
    }
    //i控制物品，j控制重量
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (j >= w[i]) {
                f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
            }
            else{
                f[i][j] = f[i - 1][j];
            }
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

vector版：

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
int n, w, i, j;
int main()
{
    cin >> w >> n;
    //定义容器行为几号物品，列为重量
    vector<vector<int>>f(n + 1, vector<int>(w+1,0));
    //定义重量与价值的容器
    vector<int>weight(n +1);
    vector<int>price(n + 1);
    //输入
    for ( i = 1; i <= n; i++) {
        cin >> weight[i] >> price[i];
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= w; j++) {
            if (j >= weight[i]) {
                f[i][j] = max(f[i - 1][j - weight[i]] + price[i], f[i - 1][j]);//比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大
            }
            else {
                f[i][j] = f[i - 1][j];//否则返回上一个物品的价值
            }
        }
    }
    cout << f[n][w] << "\n";
    return 0;
}