【Java每日一题,01背包问题】 kkksc03考前临时抱佛脚

简介: 【Java每日一题,01背包问题】 kkksc03考前临时抱佛脚

Introduction


Input


Output

输出一行,为复习完毕最短时间。

Sample

input

1 2 1 3   
5
4 3
6
2 4 3

output

20

Solution

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
/**
 * @author liangyuanshao
 * @date 2022/5/14 - 18:01
 */
public class Main {
  public static void main(String[] args) {
    Scanner s=new Scanner(System.in);
    int[] arr=new int[4];
    int time=0;
    for(int i=0;i<4;i++){
      arr[i]=s.nextInt();
    }
    for(int k=0;k<4;k++){
      int n=arr[k];
      int[] sub=new int[n+1];
      int sum=0;
      for(int i=1;i<=n;i++){
        sub[i]=s.nextInt();
        sum+=sub[i];
      }
      Arrays.sort(sub);
      int[][] bag=new int[n+1][sum/2+1];
      for (int i=1;i<=n;i++){
        for (int j=1;j<=sum/2;j++){
          bag[i][j]=bag[i-1][j];
          if(j>=sub[i]){
            bag[i][j]=Math.max(bag[i][j],bag[i-1][j-sub[i]]+sub[i]);
          }
        }
      }
      time+=(sum-bag[n][sum/2]);
    }
    System.out.println(time);
  }
}

Experience

这题目难度在于根本想不到是01背包问题,刚开始是考考虑问题使用的是贪心,题目给的例子过了,但是测试样例全错。看了题解发现考虑问题的方式很重要,一个科目的全部时间能求出来,其实就是一半脑子的时间最接近总时间的一般就行了。相当于固定空间放最大的价值。

其实样例不大,全搜索也行。


相关文章
|
7月前
|
Java
0-1背包问题(Java详解)(动态规划)至少与恰好
0-1背包问题(Java详解)(动态规划)至少与恰好
60 1
|
6月前
|
Java
01背包介绍与N皇后(dfs,考验代码能力JAVA)
01背包介绍与N皇后(dfs,考验代码能力JAVA)
|
6月前
|
算法 Java 决策智能
Java数据结构与算法:动态规划之背包问题
Java数据结构与算法:动态规划之背包问题
|
7月前
|
算法 Java
用Java实现01背包问题 用贪心算法
用Java实现01背包问题 用贪心算法
150 43
|
Java
01背包问题 java完整输入输出代码
01背包问题 java完整输入输出代码
112 0
|
算法 Java 关系型数据库
【算法数据结构Java实现】Java实现动态规划(背包问题)
1.背景      追随着buptwusuopu大神的脚步,最近在研习动态规划。动态规划应该叫一种解决问题的思想,记得又一次去某公司面试就被问到了这个。        多于动态规划的理解,大致是这样的,从空集合开始,每增加一个元素就求它的最优解,直到所有元素加进来,就得到了总的最优解。             比较典型的应用就是背包问题,有一个重量一定的包,有若干件物品,他们各自有不同的重量
1679 0
|
20天前
|
Java 开发者
Java多线程编程中的常见误区与最佳实践####
本文深入剖析了Java多线程编程中开发者常遇到的几个典型误区,如对`start()`与`run()`方法的混淆使用、忽视线程安全问题、错误处理未同步的共享变量等,并针对这些问题提出了具体的解决方案和最佳实践。通过实例代码对比,直观展示了正确与错误的实现方式,旨在帮助读者构建更加健壮、高效的多线程应用程序。 ####
|
11天前
|
缓存 Java 开发者
Java多线程编程的陷阱与最佳实践####
本文深入探讨了Java多线程编程中常见的陷阱,如竞态条件、死锁和内存一致性错误,并提供了实用的避免策略。通过分析典型错误案例,本文旨在帮助开发者更好地理解和掌握多线程环境下的编程技巧,从而提升并发程序的稳定性和性能。 ####
|
5天前
|
监控 Java 开发者
深入理解Java中的线程池实现原理及其性能优化####
本文旨在揭示Java中线程池的核心工作机制,通过剖析其背后的设计思想与实现细节,为读者提供一份详尽的线程池性能优化指南。不同于传统的技术教程,本文将采用一种互动式探索的方式,带领大家从理论到实践,逐步揭开线程池高效管理线程资源的奥秘。无论你是Java并发编程的初学者,还是寻求性能调优技巧的资深开发者,都能在本文中找到有价值的内容。 ####