Knapsack 2

题面翻译

$n$ 个物品，选取其中若干个物品，使得对选取的这些物品 $\sum w_i\leq W$ 的前提下最大化 $\sum v_i$。

其实就是背包问题。

注意数据范围与上一题不同。

题目描述

$ N $ 個の品物があります。 品物には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、品物 $ i $ の重さは $ w_i $ で、価値は $ v_i $ です。

太郎君は、$ N $ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は $ W $ であり、持ち帰る品物の重さの総和は $ W $ 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ $ : $ $ w_N $ $ v_N $

输出格式

太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。

样例 #1

样例输入 #1

1
2
3
4
3 8
3 30
4 50
5 60

样例输出 #1

1
90

样例 #2

样例输入 #2

1
2
1 1000000000
1000000000 10

样例输出 #2

1
10

样例 #3

样例输入 #3

1
2
3
4
5
6
7
6 15
6 5
5 6
6 4
6 6
3 5
7 2

样例输出 #3

1
17

提示

制約

  • 入力はすべて整数である。
  • $ 1\ \leq\ N\ \leq\ 100 $
  • $ 1\ \leq\ W\ \leq\ 10^9 $
  • $ 1\ \leq\ w_i\ \leq\ W $
  • $ 1\ \leq\ v_i\ \leq\ 10^3 $

Sample Explanation 1

品物 $ 1,\ 3 $ を選べばよいです。 すると、重さの総和は $ 3\ +\ 5\ =\ 8 $ となり、価値の総和は $ 30\ +\ 60\ =\ 90 $ となります。

Sample Explanation 3

品物 $ 2,\ 4,\ 5 $ を選べばよいです。 すると、重さの総和は $ 5\ +\ 6\ +\ 3\ =\ 14 $ となり、価値の総和は $ 6\ +\ 6\ +\ 5\ =\ 17 $ となります。

题解

题目解析

一道比较奇怪的背包dp,仔细看 $ 1\ \leq\ W\ \leq\ 10^9 $ , 背包容量竟然超过了1e9.那么平常的背包就无法解决了.

我们需要想一个比较取巧的方法,观察价值仅仅只有1e3,那么我们可以逆向思维:既然无法由背包容量来推导,那么我们是否可以反向推导背包的价值呢?

答案是肯定的,我们可以这么考虑:把dp这个数组的容量看作 组成价值为i物品的最小容量消耗 ,那么我们可以顺利的得到状态转移方程:

解释一下:

dp[i]:组成i价值的背包所需要的最少容量;

min中前一个dp[i]:上一次已经组成i价值了(容量要继承),这次选择不选它.

min中后一个dp[i-v[i]]+w[i]:上一次组成了i-v[i]的价值,这次选择这个物品所以要在dp[i-v[i]]的基础上再加上w[i]的容量

AC代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(1e5);
int a[3][110];
ll dp[MAXN];

signed main(){
    CIN;CIN_;
    int n,w;
    cin >> n >> w;
    int MAX = 1000*n;
    fa(1,n,1){
    	cin >> a[1][i] >> a[2][i];
    }
    mem(dp,0x3f3f3f3f);
    dp[0] = 0;
    fa(1,n,1){
    	for(int j=MAX;j>=a[2][i];j--){
    		dp[j] = min(dp[j],dp[j-a[2][i]]+a[1][i]);
    	}
    }
    fb(MAX,1,1){
    	if(dp[i] <= w){
    		cout << i << endl;
    		break;
    	}
    }
    return 0;
}