装箱问题

[编程题]装箱问题

热度指数：6685 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述:

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述:

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

示例1

输入

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var v int
    fmt.Scan(&v)
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scan(&arr[i])
    }
    dp:=make([]int,v+1)
    for _,x:=range arr{
        for i:=v;i>=x;i--{
            dp[i]=max(dp[i],x+dp[i-x])
        }
    }
    fmt.Print(v-dp[v])
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-02-12 11:37:05 回复(0)