Skip to content

11613: 【原1613】Interesting Knapsack

题目

题目描述

author: xzj 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1613

Description

存在N个物品,第i个物品有重量wi与价值vi,并且第i个物品可能依赖于第j件物品。

依赖的意思是指,你如果想购买第i个物品,必须购买过第j件物品。保证依赖关系不会构成环,并且每件物品至多存在一个依赖的物品。

求给定背包可容纳重量后,你可以装最多多少价值的物品。

Input Format

第1行,两个整数N,W,代表物品个数以及背包容量。

第2~N+1行,每行三个整数Fi, Wi, Vi,代表第i个物品的依赖物品,重量,价值。

注意,物品从1开始编号,当Fi=0的时候,意味着该物品不需要依赖任何其他物品。

Output Format

一个整数,代表最大价值和。

Sample Input 1

5 5
0 1 2
0 2 3
0 3 5
0 4 4
0 5 7

Sample Output 1

8

Sample Input 2

5 5
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1000

Sample Output 2

5

Data

  • 对于30%的数据,满足 N<=18(该部分其中一半数据,全部的物品Fi=0);
  • 对于另外30%的数据,满足 N<=1000(全部的物品Fi=0);
  • 对于另外20%的数据,满足 N<=100;
  • 对于100%的数据,满足 N<=1000.
  • W与N数据范围一致。
  • Wi,Vi全部为非负整数,答案在int以内.

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1613.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, W;
int f[1005], w[1005], v[1005];
int lis[1005], lis_len = 0;
int dp[1005][8005] = {0};
int to[1005], at[1005] = {0}, nxt[1005], cnt = 0;
int du[1005] = {0};
int tim[1005], D = 0, siz[1005] = {0};
void ddfs(int cur){
    siz[cur] = 1;
    for (int i = at[cur]; i; i = nxt[i])
        ddfs(to[i]), siz[cur] += siz[to[i]];
    tim[++D] = cur;
}
void init(){
    n = read(), W = read();
    for (int i = 1; i <= n; ++i){
        f[i] = read(), w[i] = read(), v[i] = read();
        if (f[i] > 0) 
            to[++cnt] = i, nxt[cnt] = at[f[i]], at[f[i]] = cnt, ++du[i];
    }
    w[n + 1] = v[n + 1] = 0;
    for (int i = 1; i <= n; ++i){
        if (du[i]) continue;
        if (at[i] > 0){
            to[++cnt] = i, nxt[cnt] = at[n + 1], at[n + 1] = cnt;
        }else {
            lis[++lis_len] = i;
        }
    }
    ddfs(n + 1);
}
void solve(){
    for (int i = 1; i <= D; ++i){
        int iid = tim[i];
        int ww = w[iid], vv = v[iid];
        for (int j = 0; j <= W; ++j){
            int cdt = dp[i - siz[iid]][j];
            if (j >= ww) cdt = max(cdt, dp[i - 1][j - ww] + vv);
            dp[i][j] = cdt;
        }
    }
    for (int i = 1; i <= lis_len; ++i){
        int ww = w[lis[i]], vv = v[lis[i]];
        for (int j = W; j >= ww; --j)
            dp[D][j] = max(dp[D][j], dp[D][j - ww] + vv);
    }
    printf("%d\n", dp[D][W]);
}
int main(){
    init();
    solve();
    return 0;
}