题解 | #【模板】完全背包#

【模板】完全背包

http://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//物品数量
        int v = input.nextInt();//背包容量
        int[] vol = new int[n + 1]; //体积
        int[] val = new int[n + 1]; //价值
        for (int i = 0; i < n; i++) {
            vol[i + 1] = input.nextInt();
            val[i + 1] = input.nextInt();
        }
        
        int[] dp = new int[v+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= v; j++){
                if(j >= vol[i]){
                    //无限背包和01背包基本类似,区别就在于物品是否唯一,
                    //如果物品唯一,就从后向前填,这样每次值的更新都是基于没放该物品的情况,相当于只放了一件
                    //如果物品不唯一,就从前向后填,这样如果容量足以放重复的物品时,会基于前面放过的情况累加,相当于放了多件
                    dp[j] = Math.max(dp[j], dp[j - vol[i]] + val[i]);
                }
            }
        }
        System.out.println(dp[v]);
        
        Arrays.fill(dp,Integer.MIN_VALUE);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= v; j++){
                if(j >= vol[i]){
                    dp[j] = Math.max(dp[j], dp[j - vol[i]] + val[i]);
                }
            }
        }
        if(dp[v]<0){
            dp[v] = 0;
        }
        System.out.println(dp[v]);
    }
}

全部评论

相关推荐

05-03 12:45
西南大学 Java
nsnzkv:你这项目写的内容太多了,说实话都是在给自己挖坑,就算简历过了,后面面试也难受
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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