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

  1. 第一类物品只能用1次(01背包);
  2. 第二类物品可以用无限次(完全背包);
  3. 第三类物品最多只能用 si 次(多重背包);

每种物品有体积 vi 和价值 wi。 要求将哪些物品装入背包,使物品体积总和不超过背包容量,且价值总和最大。

输入格式

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

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

  • si = -1 表示第 i 种物品只能用1次;
  • si = 0 表示第 i 种物品可以用无限次;
  • si > 0 表示第 i 种物品可以使用 si 次;

输出格式

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

数据范围

  • 0 < N, V ≤ 1000
  • 0 < vi, wi ≤ 1000
  • -1 ≤ si ≤ 1000

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例

8

代码实现

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

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;
        if (!s) {
            for (int i = v; i <= V; ++i)
                dp[i] = max(dp[i], dp[i - v] + w);
        }
        else {
            s = abs(s);
            int t = 1;
            while(t <= s) {
                for (int i = V; i >= t * v; --i)
                    dp[i] = max(dp[i], dp[i - t * v] + t * w);
                s -= t;
                t <<= 1;
            }
            if (s) 
                for (int i = V; i >= s * v; --i)
                    dp[i] = max(dp[i], dp[i - s * v] + s * w);
        }
    }
    cout << dp[V];
    return 0;
} 
分类: AlgorithmDP

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status