【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详解)(动态规划)至少与恰好
58 1
|
6月前
|
Java
01背包介绍与N皇后(dfs,考验代码能力JAVA)
01背包介绍与N皇后(dfs,考验代码能力JAVA)
|
6月前
|
算法 Java 决策智能
Java数据结构与算法:动态规划之背包问题
Java数据结构与算法:动态规划之背包问题
|
7月前
|
算法 Java
用Java实现01背包问题 用贪心算法
用Java实现01背包问题 用贪心算法
149 43
|
Java
01背包问题 java完整输入输出代码
01背包问题 java完整输入输出代码
112 0
|
算法 Java 关系型数据库
【算法数据结构Java实现】Java实现动态规划(背包问题)
1.背景      追随着buptwusuopu大神的脚步,最近在研习动态规划。动态规划应该叫一种解决问题的思想,记得又一次去某公司面试就被问到了这个。        多于动态规划的理解,大致是这样的,从空集合开始,每增加一个元素就求它的最优解,直到所有元素加进来,就得到了总的最优解。             比较典型的应用就是背包问题,有一个重量一定的包,有若干件物品,他们各自有不同的重量
1679 0
|
12天前
|
Java 开发者
Java多线程编程中的常见误区与最佳实践####
本文深入剖析了Java多线程编程中开发者常遇到的几个典型误区,如对`start()`与`run()`方法的混淆使用、忽视线程安全问题、错误处理未同步的共享变量等,并针对这些问题提出了具体的解决方案和最佳实践。通过实例代码对比,直观展示了正确与错误的实现方式,旨在帮助读者构建更加健壮、高效的多线程应用程序。 ####
|
3天前
|
缓存 Java 开发者
Java多线程编程的陷阱与最佳实践####
本文深入探讨了Java多线程编程中常见的陷阱,如竞态条件、死锁和内存一致性错误,并提供了实用的避免策略。通过分析典型错误案例,本文旨在帮助开发者更好地理解和掌握多线程环境下的编程技巧,从而提升并发程序的稳定性和性能。 ####
|
3天前
|
安全 Java 开发者
Java中的多线程编程:从基础到实践
本文深入探讨了Java多线程编程的核心概念和实践技巧,旨在帮助读者理解多线程的工作原理,掌握线程的创建、管理和同步机制。通过具体示例和最佳实践,本文展示了如何在Java应用中有效地利用多线程技术,提高程序性能和响应速度。
24 1