ACW1019.庆功会

1. 题目

• 活动 - AcWing

• 为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

• 期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

输入格式

• 第一行二个数 n，m，其中 n 代表希望购买的奖品的种数，m表示拨款金额。
• 接下来 n 行，每行 3 个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0 件到 s 件均可）。

输出格式

• 一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

数据范围

$n\le 500,m\le 6000$,
$v\le 100,w\le 1000,s\le 10$

输入样例

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

输出样例

1040

2. 思路

• 某个奖品最多可以买 s 次，可以视作普通的 s 个物品，那么退化成简单的 01 背包问题即可。

3. 代码

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {

	in := bufio.NewReader(os.Stdin)

	var n, m int
	fmt.Fscan(in, &n, &m)

	var v = make([]int, n)
	var w = make([]int, n)
	var s = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &v[i], &w[i], &s[i])
	}

	f := make([]int, m+1)
	for i := 0; i < n; i++ {
		currentCost := v[i]
		for j := 0; j < s[i]; j++ {
			for k := m; k >= currentCost; k-- {
				f[k] = maxx(f[k], f[k-currentCost]+w[i])
			}
		}
	}

	fmt.Println(f[m])
}

func maxx(nums ...int) int {
	res := nums[0]
	for _, v := range nums {
		if v > res {
			res = v
		}
	}
	return res
}