链家2018链习生招聘考试-编程题一

发表于 | 分类于 ，

题目

描述

玥玥带乔乔一起逃亡,现在有许多东西要放到乔乔的包里面,
但是包的大小有限,所以我们只能够在里面放入非常重要的物品.
现在给出该种物品的数量,体积,价值的数值,
希望你能够算出怎样能使背包的价值最大的组合方式,
并且输出这个数值,乔乔会非常感谢你的

输入

第 1 行有两个整数,物品种数 n 和背包装载体积v;
第 2 到 n+1 行每行三个整数,为第 i 种物品的数量 m,体积 v,价值s

输出

仅包含一个整数,即为能拿到的最大的物品价值总和

Example

Input

2 10
3 4 3
2 2 5

Output

13

题解

动态规划

  • 定义 value(i,j) 为在背包装载体积为 i,物品为第 1 到 j 个的情况下,背包的最大价值
  • value(v,sum(m[i])) 即为所求
  • 可以把空间复杂度从 O(nv) 降到 O(v)
  • 状态转移方程:
1
2
value(i,j) = |-> max(value(i-w[j],j-1)+s[j],value(i-1,j-1) (i-w[j] >= 0)
             |-> value(i-1,j-1) (i-w[j] < 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;

int n,m,v,c=0,maxs=0,value[501],w[20001],s[20001];

int main()
{
    memset(value,0,sizeof value);
    cin>>n>>v;
    for(int i=1,j=1;i<=n;++i)
    {
        scanf("%d%d%d",&m,&w[j],&s[j]);
        c+=m;
        int k=1;
        for(;k<m;++k)
        {
            w[k+j]=w[j],s[k+j]=s[j];
        }
        j+=k;
    }
    for(int j=1;j<=c;++j)
    {
        for(int i=v;i>0;--i)
        {
            int k=i-w[j];
            value[i]=(k>=0?max(value[k]+s[j],value[i-1]):value[i-1]);
        }
    }
    cout<<value[v];
}