完全背包

[编程题]完全背包

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

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为 $v_i$ ,价值为 $w_i$ 。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

数据范围： $1 \le v,v_i,w_i \le 1000 \$

示例1

输入

6,2,[[5,10],[3,1]]

输出

[10,2]

示例2

输入

8,3,[[3,10],[9,1],[10,1]]

输出

[20,0]

说明

无法恰好装满背包。

示例3

输入

13,6,[[13,189],[17,360],[19,870],[14,184],[6,298],[16,242]]

输出

[596,189]

说明

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

算法知识视频讲解

七月牧夫

func knapsack( v int ,  n int ,  nums [][]int ) []int {
    dp,dp1 := make([]int, v + 1),  make([]int, v + 1)
    for tmpV := 1; tmpV <= v; tmpV++ { // 遍历容量v作为状态复用
        max, max1 := 0, 0
        for i := 1; i <= len(nums);i++ {
            iv := nums[i - 1][0]
            iw := nums[i - 1][1]

            if tmpV >= iv {
                // 1. 放入第i种物品刚好得到最大价值
                if max < dp[tmpV - iv] +iw { 
                    max = dp[tmpV - iv] +iw
                }
                //2 第j种物品刚好填满i个容量 得到最大价值
                if (tmpV - iv == 0 || dp1[tmpV - iv] != 0) && max1 < dp1[tmpV - iv] + iw { 
                    max1 = dp1[tmpV - iv] + iw
                }
            } 
        }
        dp[tmpV], dp1[tmpV] = max, max1
    }
    return []int{dp[v], dp1[v]}
}

发表于 2023-07-20 22:10:00 回复(0)