题解 | #【模板】01背包#

【模板】01背包

http://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e

01 背包问题,利用一维滚动数组进行优化 初始化条件: 初始化为负无穷化代表不可能装满 背包的容量为0,也为装满了,是一种可行的情况,则初始化为0

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int V = reader.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            v[i] = reader.nextInt();
            w[i] = reader.nextInt();
        }
        int[] dp = new int[V + 1];
        Arrays.fill(dp, Integer.MIN_VALUE + 10001);
        dp[0] = 0;
        // init
        // dp[i][j] = dp[i - 1][j], dp[i - 1][j - v[i]]
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        int res = 0;
        for (int i = 1; i <= V; i++) {
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
        System.out.println(dp[V] > 0 ? dp[V]: 0);
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
06-07 00:00
已编辑
腾讯_后端开发
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-16 14:00
白火同学:其实你可以了解一下HR在Boss聊天的机制,想赢牌的前提是先会玩牌。 如果HR长时间没有理你,有可能是因为你的消息被其他应聘者的消息给挤到下面了,HR从上到下有可能只看个三四百个人就要到理想数量的简历了,而你恰好没有被看到,时间一长,你的消息在越来越下面。这种情况就需要你自己活跃一下,把消息提上去。 也可能是HR招的合适的人选了,但会一直挂着岗位,为了省重新开招聘岗位的钱,方便后面随时修改招聘要求。 当然也可能是HR吃饱了没事耍你玩,要了你的简历又不看,就看你自己怎么理解了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务