美文网首页
java算法巩固训练day01

java算法巩固训练day01

作者: dev_winner | 来源:发表于2019-07-11 11:04 被阅读0次

01背包

package Test.demo;

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
//            int n = in.nextInt();
//            int V = in.nextInt();
//            int[] dp = new int[V + 1];
//            int[] v = new int[n + 1];
//            int[] w = new int[n + 1];
//            for(int i = 0; i < n; ++i) {
//                v[i] = in.nextInt();
//                w[i] = in.nextInt();
//            }
//            for(int i = 0; i < n; ++i) { // 二维优化成一维
//                for(int j = V; j >= v[i]; --j) { // 注意是从大到小的顺序
//                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
//                }
//            }
//            System.out.println(dp[V]);
            int n = in.nextInt();
            int V = in.nextInt();
            int[][] dp = new int[n + 1][V + 1];
            int[] w = new int[n + 1];
            int[] v = new int[n + 1];
            for(int i = 1; i <= n; ++i) {
                w[i] = in.nextInt();
                v[i] = in.nextInt();
            }
            for(int i = 1; i <= n; ++i) {
                for(int j = 0; j <= V; ++j) {  // 二维数组，从小到大，选与不选
                    if(j >= w[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                    else dp[i][j] = dp[i - 1][j];
                }
            }
            System.out.println(dp[n][V]);
        }
        out.close();
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}

完全背包

package Test.demo;


import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
//            int n = in.nextInt();
//            int V = in.nextInt();
//            int[] w = new int[n + 1];
//            int[] v = new int[n + 1];
//            int[][] dp = new int[n + 1][V + 1];
//            for(int i = 1; i <= n; ++i) {
//                w[i] = in.nextInt();
//                v[i] = in.nextInt();
//            }
//            // 二维数组实现完全背包
//            for(int i = 1; i <= n; ++i) {
//                for(int j = 0; j <= V; ++j) {
//                    if(j >= w[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
//                    else dp[i][j] = dp[i - 1][j];
//                }
//            }
//            System.out.println(dp[n][V]);
            // 一维数组实现完全背包
            int n = in.nextInt();
            int V = in.nextInt();
            int[] dp = new int[V + 1];
            int[] w = new int[n + 1];
            int[] v = new int[n + 1];
            for(int i = 1; i <= n; ++i) {
                w[i] = in.nextInt();
                v[i] = in.nextInt();
            }
            for(int i = 1; i <= n; ++i) {
                for(int j = w[i]; j <= V; ++j) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            }
            System.out.println(dp[V]);
        }
        out.close();
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}

多重背包

package Test.demo;

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
            int n = in.nextInt();
            int V = in.nextInt();
            int[] w = new int[n + 1];
            int[] v = new int[n + 1];
            int[] s = new int[n + 1];
            int[] dp = new int[V + 1];
            for(int i = 0; i < n; ++i) {
                w[i] = in.nextInt();
                v[i] = in.nextInt();
                s[i] = in.nextInt();
            }
            for(int i = 0; i < n; ++i){
                for(int j = V; j >= w[i]; --j) {
                    for(int k = 1; k <= s[i] && k * w[i] <= j; ++k) {
                        // 枚举装入的数量，注意每种物品的数量上限，把每件物品看成单件物品，暴力枚举
                        dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
                    }
                }
            }
            System.out.println(dp[V]);
        }
        out.close();
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}

多重背包二进制优化算法

package Test.demo;

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    static int[] dp = new int[2005]; // 申请静态全局变量
    static int n, V;
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
            n = in.nextInt();
            V = in.nextInt();
            Arrays.fill(dp, 0); // 注意将数组全部填充为0
            int[] w = new int[n + 1];
            int[] v = new int[n + 1];
            int[] s = new int[n + 1];
            for(int i = 0; i < n; ++i) {
                w[i] = in.nextInt();
                v[i] = in.nextInt();
                s[i] = in.nextInt();
                MultiplePack(w[i], v[i], s[i]);
            }
            System.out.println(dp[V]);
        }
        out.close();
    }
    public static void ZeroOnePack(int w, int v) { //01背包
        for(int j = V; j >= w; --j) {
            dp[j] = Math.max(dp[j], dp[j - w] + v);
        }
        return;
    }
    public static void CompletePack(int w, int v) { // 完全背包
        for(int j = w; j <= V; ++j) {
            dp[j] = Math.max(dp[j], dp[j - w] + v);
        }
        return;
    }
    public static void MultiplePack(int w, int v, int num) {  // 多重背包
        if(w * num >= V) CompletePack(w, v);  // 默认当成完全背包来计算
        else {
            for(int k = 1; k <= num; k <<= 1) { // 二进制优化算法
                ZeroOnePack(w * k, v * k);
                num -= k;
            }
            if(num > 0) ZeroOnePack(w * num, v * num);
        }
        return;
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}

相关文章

网友评论

      本文标题：java算法巩固训练day01

      本文链接：https://www.haomeiwen.com/subject/atzlkctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|java算法巩固训练day01|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！