文档章节

背包问题

a_xianyu
 a_xianyu
发布于 2017/09/04 14:42
字数 1112
阅读 13
收藏 0
点赞 0
评论 0

01背包:   

    01背包的状态转换方程:f(i, j) = max{f(i-1, j), f(i - 1, j - wi) + vi (j >= wi) }

    f(i, j)表示在前i件物品中选择若干件物品放入承重为j的背包中,可以取得的最大价值,其中vi表示第i件物品的价值。其实也就是从f(i-1, j)到f(i, j)的过程中,判断是否应该放入第i件物品。

例:(原题:http://acm.nyist.net/JudgeOnline/problem.php?pid=860,改成简单版了)

    有N个重量和价值分别为wi 和 vi 的 物品,从这些物品中选择总重量不超过 W 的物品,求所有挑选方案中物品价值总和的最大值。  

1 <= N <=100
1 <= W <= 1000
1 <= wi <= 10
1 <= vi <= 100

输入

    多组测试数据。

    每组测试数据第一行输入,N 和 W ,接下来有N行,每行输入两个数,代表第i个物品的wi 和 vi。

    每组测试数据第一行

输出

    满足题意的最大价值,每组测试数据占一行。

提供两组测试数据:

5 10
4 6
5 4
6 5
2 3
2 6

结果15

4 5
2 3
1 2
3 4
2 2

结果7

import java.util.Scanner;

/**
 * @create 2017-09-04 8:51
 */
public class Main {
    public static int N, W;

    public static int process(Item[] items) {
        int[][] h = new int[items.length][W + 1];
        for (int i = 0; i < items.length; i++) {
            for (int j = 1; j < W + 1; j++) {
                if (i == 0) {
                    if (items[i].w <= j) {
                        h[i][j] = items[i].v;
                    }
                } else {
                    if (items[i].w <= j) {
                        h[i][j] = Math.max(h[i - 1][j], h[i - 1][j - items[i].w] + items[i].v);
                    } else {
                        h[i][j] = h[i - 1][j];
                    }
                }
            }
        }
        return h[items.length - 1][W];
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            N = input.nextInt();
            W = input.nextInt();
            Item[] items = new Item[N];
            for (int i = 0; i < N; i++) {
                items[i] = new Item(input.nextInt(), input.nextInt());
            }
            System.out.println(process(items));
        }
        input.close();
    }

    static class Item {
        int w;
        int v;

        public Item(int w, int v) {
            this.w =  w;
            this.v = v;
        }
    }
}

    当然,可以进行空间压缩,将二维数组转换为一维数组。此时状态转换方程为

            f(j) = max(f(j), f(j-wi) + vi)) (j >= wi)

    此时背包容量采用倒序进行计算

import java.util.Scanner;

/**
 * @create 2017-09-04 8:51
 */
public class Main {
    public static int N, W;

    public static int process(Item[] items) {
        int[] h = new int[W + 1];
        for (int i = 0; i < items.length; i++) {
            for (int j = W; j >= items[i].w; j--) {
                h[j] = Math.max(h[j], h[j-items[i].w] + items[i].v);
            }
        }

        return h[W];
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            N = input.nextInt();
            W = input.nextInt();
            Item[] items = new Item[N];
            for (int i = 0; i < N; i++) {
                items[i] = new Item(input.nextInt(), input.nextInt());
            }
            System.out.println(process(items));
        }
        input.close();
    }

    static class Item {
        int w;
        int v;

        public Item(int w, int v) {
            this.w =  w;
            this.v = v;
        }
    }
}

二维背包:

链接:https://www.nowcoder.com/questionTerminal/b8bc8459f0d34aaa8c1af1328cab2432
来源:牛客网

众所周知计算机代码底层计算都是0和1的计算,牛牛知道这点之后就想使用0和1创造一个新世界!牛牛现在手里有n个0和m个1,给出牛牛可以创造的x种物品,每种物品都由一个01串表示。牛牛想知道当前手中的0和1可以最多创造出多少种物品。

输入描述:

输入数据包括x+1行:
第一行包括三个整数x(2 ≤ x ≤ 20),n(0 ≤ n ≤ 500),m(0 ≤ m ≤ 500),以空格分隔
接下来的x行,每行一个01串item[i],表示第i个物品。每个物品的长度length(1 ≤ length ≤ 50)

输出描述:

输出一个整数,表示牛牛最多能创造多少种物品

示例1

输入

3 3 1
1
00
100

输出

2

ps: 由于题意过于模糊,在次稍作解释。题目要求的是利用给定的n个0和m个1,最多可以同时得到多少种给定的字符串。对于实例,也就是用3个1和1个0可以如何组合得到{1, 00, 100}中最多的组合数,显然是1和00,也就是输出结果中的2。

    状态转移方程:dp[u][v] = max(dp[u-a[i]][v-b[i]]+w[i],dp[u][v]) (u, v均采用倒序)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int x = sc.nextInt();
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] zero = new int[x];
            int[] one = new int[x];
            String item;
            for (int i = 0; i < x; i++) {
                item = sc.next();
                int cnt = 0;
                for (int j = 0; j < item.length(); j++) {
                    if (item.charAt(j) == '0') {
                        cnt++;
                    }
                }
                zero[i] = cnt;
                one[i] = item.length() - cnt;
            }
            int[][] dp = new int[n + 1][m + 1];
            for (int i = 0; i < x; i++) {
                for (int j = n; j >= zero[i]; j--) {
                    for (int k = m; k >= one[i]; k--) {
                        if (dp[j][k] < dp[j - zero[i]][k - one[i]] + 1) {
                            dp[j][k] = dp[j - zero[i]][k - one[i]] + 1;
                        }
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }
}

 

© 著作权归作者所有

共有 人打赏支持
a_xianyu
粉丝 0
博文 36
码字总数 18533
作品 0
哈尔滨
程序员

暂无文章

面试系列-40个Java多线程问题总结

前言 这篇文章主要是对多线程的问题进行总结的,因此罗列了40个多线程的问题。 这些多线程的问题,有些来源于各大网站、有些来源于自己的思考。可能有些问题网上有、可能有些问题对应的答案也...

Ryan-瑞恩
10分钟前
0
0
微信分享的细节

分享的缩略图要求: 一、图片大小小于32k 二、图片的尺寸为 宽度 :128px 高度:128px 分享title 和 description 出现金额等 以上情况存在会导致触发分享按钮 但是页面没有反应...

Js_Mei
15分钟前
0
0
【2018.07.23学习笔记】【linux高级知识 Shell脚本编程练习】

1、编写shell脚本,计算1-100的和; #!/bin/bashsum=0for i in `seq 1 100`do sum=$[$sum+$i]doneecho $sum 2、编写shell脚本,要求输入一个数字,然后计算出从1到输入数字的和,要求...

lgsxp
18分钟前
0
0
xss攻防浅谈

导读 XSS (Cross-Site Script) 攻击又叫跨站脚本攻击, 本质是一种注入攻击. 其原理, 简单的说就是利用各种手段把恶意代码添加到网页中, 并让受害者执行这段脚本. XSS能做用户使用浏览器能做的...

吴伟祥
18分钟前
0
0
js回调的一次应用

function hideBtn(option) { if (option == 1) { $("#addBtn").hide(); $("#addSonBtn").hide(); }}$("body").on("click", "#selectBtn", function () {......

晨猫
24分钟前
0
0
C++_读写ini配置文件

1.WritePrivateProfileString:

一个小妞
24分钟前
0
0
通往阿里,BAT的50+经典Java面试题及答案解析(上)

Java是一个支持并发、基于类和面向对象的计算机编程语言。下面列出了面向对象软件开发的优点: 代码开发模块化,更易维护和修改。 代码复用。 增强代码的可靠性和灵活性。 增加代码的可理解性...

Java大蜗牛
24分钟前
1
0
数据库两大神器【索引和锁】

前言 只有光头才能变强 索引和锁在数据库中可以说是非常重要的知识点了,在面试中也会经常会被问到的。 本文力求简单讲清每个知识点,希望大家看完能有所收获 声明:如果没有说明具体的数据库...

Java3y
28分钟前
0
0
Application Express安装

Application Express安装文档 数据库选择和安装 数据库选择 Oracle建议直接12.2.0.1.0及以上的版本,12.1存在20618595bug(具体可参见官方文档) Oracle 12c 中安装oracle application expr...

youfen
40分钟前
0
0
OpenMessaging概览

序 本文主要研究一下OpenMessaging 架构图 namespace,类似cgroup的namespace,用来进行安全隔离,每个namespace有自己的producer、consumer、topic、queue等 producer,消息生产者有两类,一...

go4it
45分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部