cht的个人网站

欢迎鉴临

主页 题解 分享 资源 设置 应用 反馈 关于

cht的部分题解

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
        4 5
        1 2
        2 4
        3 4
        4 5
        输出样例:
        8
        

算法1

C++ 代码

#include <iostream>
        using namespace std;
        const int N = 1010;
        int n, m,v[N], w[N],f[N];
        int main()
        {
            cin >> n >> m;
            for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
            for (int i = 1; i <= n; i ++ )
                for (int j = m; j >= v[i]; j -- )
                    f[j] = max(f[j], f[j - v[i]] + w[i]);
            cout << f[m];
        }
        

抽风大佬的空间优化版

#include <iostream>
        using namespace std;
        int f[1005];
        int n, m;
        int main()
        {
            cin >> n >> m;
            for (int i = 1; i <= n; i ++ )
            {
                int v, w;
                cin >> v >> w;
                for (int j = m; j >= v; j -- )
                    f[j] = max(f[j], f[j - v] + w);
            }
            cout << f[m];
            return 0;
        }