有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 < N, V ≤ 100
0 < vi, wi, si ≤ 100

输入样例

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

输出样例

10

代码实现

朴素DP

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3;

int n, V, v, w, s, 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 >> w >> s;
        for (int j = 0; j <= V; ++j) {
            for (int k = 0; k <= s && k * v <= j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v] + k * w);
            }
        }
    }
    cout << dp[n][V];
    return 0;
} 

滚动数组优化 + DP

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

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

二进制优化 + 滚动数组优化 + DP

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

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

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status