ACW1024.装箱问题

1. 题目

• 活动 - AcWing

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

第一行是一个整数 V，表示箱子容量。 第二行是一个整数 n，表示物品数。 接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

数据范围

$0<V\le 20000$,
$0<n\le 30$

输入样例

24
6
8
3
12
7
9
7

输出样例

0

2. 思路

• 基本的 01 背包问题，在背包体积就是箱子大小的情况下，背包内物品的总体积越大越好
• 相当于物品的贡献就是本身的体积

3. 代码

package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	// defer file.Close()

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

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

	// f[i] = x; max Volume is i, max profit is x
	f := make([]int, v+1)
	for i := 0; i < n; i++ {
		currentCost := arr[i]
		for k := v; k >= currentCost; k-- {
			f[k] = maxx(f[k], f[k-currentCost]+arr[i])
		}
	}

	fmt.Println(v - f[v])
}

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