通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1

1
2
3
4
45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

1
10

提示

$1 \leq m, n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

题解

题目解析

一道分组背包,但是一组内只能选一个.我卡在了一个地方:如何一组内只选一个物品呢?

看了别人的代码,才知道只需要把背包容量遍历和遍历同一组物品的for循环换个位置就好了…

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 <stack>
#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(1e3);
int v1[110][MAXN][3],v2[110];
ll dp[MAXN];

signed main(){
	int m,n,cunt=0;
	cin >> m >> n;
	fa(1,n,1){
		int v,p,q;
		cin >> v >> p >> q;
		if(v2[q]++ == 0) ++cunt;
		v1[q][v2[q]][1] = v;
		v1[q][v2[q]][2] = p;
	}
	fa(1,cunt,1){
		for(int j=m;j>=0;j--){//只需要把背包容量循环放到外面就好了
			for(int k=1;k<=v2[i];k++){
				if(j >= v1[i][k][1]){
					dp[j] = max(dp[j],dp[j-v1[i][k][1]]+v1[i][k][2]);
				}
			}
		}
	}
	cout << dp[m] << endl;
	return 0;
}