AT_tdpc_knapsack ナップザック
题目描述
# AT683 背包
有$N$个物品，第i个重$w_i$，价值是$v_i$，颜色是$c_i$。背包可以容纳总重量小于$W$，颜色总数小于$C$的物品。问拿到的物品价值总和最大是多少？
输入格式
$N\ W\ C$
$w_1\ \ v_1\ \ c_1$
$\ \vdots\quad\ \vdots\quad\vdots$
$w_N\ v_N\ c_N$
输出格式
一行，拿到的物品最大价值总和。
说明/提示
- $1\le N\le100$
- $1\le W\le10000$
- $1\le C\le50$
- $1\le w_i,v_i\le10000$
- $1\le c_i\le50$
**样例数据**
输入：
```
4 5 2
1 10 1
1 20 2
1 30 3
10 100 4
```
输出：
```
50
```
选择第二、三个物品
---
输入：
```
10 20 2
4 5 6
3 3 9
5 2 9
4 1 6
6 8 3
3 7 6
2 4 9
4 7 3
6 5 6
3 2 9
```
输出：
```
27
```