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

每件物品的信息如下:

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

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

输入格式

  • 第一行:两个整数 NV,用空格隔开,分别表示物品数量和背包容积。
  • 接下来有 N 行,每行两个整数 viwi,用空格隔开,表示第 i 件物品的体积和价值。

输出格式

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

数据范围

  • 0 < N, V ≤ 1000
  • 0 < vi, wi ≤ 1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

代码实现

DP

  • T(n) = O(n * v)
  • S(n) = O(n ^ 2)
#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int w[N], v[N], n, V, dp[N][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; ++i) {
        int p = 0;
        while(p < v[i]) dp[i][p++] = dp[i - 1][p];
        while(p <= V) dp[i][p++] = max(dp[i - 1][p], dp[i - 1][p - v[i]] + w[i]);
    }
    cout << dp[n][V];
    return 0;
} 

滚动数组优化

  • T(n) = O(n * v)
  • S(n) = O(v)
#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int n, V, w, v, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    while(n--) {
        cin >> v >> w;
        for (int i = V; i >= v; --i) dp[i] = max(dp[i], dp[i - v] + w);
    }
    cout << dp[V];
    return 0;
} 
分类: AlgorithmDP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status