N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M

每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi

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

输入格式

第一行三个整数,N, V, M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。

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

输出格式

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

数据范围

0 < N ≤ 1000 0 < V, M ≤ 100 0 < vi, mi ≤ 100 0 ≤ wi ≤ 1000

输入样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例

8

代码实现

#include <iostream>
using namespace std;
const int N = 110;

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

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status