01背包

[编程题]01背包

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

已知一个背包最多能容纳体积之和为v的物品

现有 n 个物品，第 i 个物品的体积为 v_i , 重量为 w_i

求当前背包最多能装多大重量的物品?

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

进阶： $O(n \cdot v)$

示例1

输入

10,2,[[1,3],[10,4]]

输出

说明

第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4

示例2

输入

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

输出

说明

两个物品体积之和等于背包能装的体积，所以两个物品都取是最优方案

算法知识视频讲解

JavaScript

别卷啦！

https://blog.csdn.net/achesong/article/details/88428895

function knapsack( V ,  n ,  vw ) {
    // write code here
    if (V == 0 || n == 0 || vw.length == 0) {
     return 0;
 }
    const dp = Array.from(new Array(n+1),()=>new Array(V+1).fill(0))
    for(let i = 1;i<=n;i++){
        for(let j = 1;j<=V;j++){
            if(j<vw[i-1][0]){
                dp[i][j] = dp[i-1][j]
            }else{
                let v1 = dp[i-1][j]
                let v2 = dp[i-1][j-vw[i-1][0]]+vw[i-1][1]
                dp[i][j] = Math.max(v1, v2)
            }
        }
    }
    return dp[n][V]
}

发表于 2021-01-25 20:00:16 回复(1)