文档章节

背包问题

a_xianyu
 a_xianyu
发布于 2017/09/04 14:42
字数 1112
阅读 17
收藏 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
哈尔滨
程序员
私信 提问

暂无文章

【PG内核】pg11秒级新增非空默认字段的实现方法

pg11新特性,可以瞬间向一个表中添加非空默认字段。 今天研究了一下这个特性的内核实现方式,写个博客简单记录一下。 结论奉上 pg在从硬盘或者内存获取到一条数据记录后(以下称tuple),会使...

movead
16分钟前
0
0
如何保证MongoDB的安全性?

上周写了个简短的新闻《MongoDB裸奔,2亿国人求职简历泄漏!》: 根据安全站点HackenProof的报告,由于MongoDB数据库没有采取任何安全保护措施,导致共计202,730,434份国人求职简历泄漏。 然...

Fundebug
22分钟前
0
0
KVM

目录 (1):简介及安装 1. KVM 介绍 1.0 虚拟化简史 1.1 KVM 架构 2. KVM 的功能列表 3. KVM 工具集合 4. RedHat Linux KVM 安装 4.1 在安装 RedHat Linux 时安装 KVM 4.2 在已有的 RedHat...

临江仙卜算子
37分钟前
0
0
脚本配置java开发环境

@echo off&setlocal enabledelayedexpansion cls @echo "This script is used to registe envionment variables......" @echo. @echo. @echo. set var=%~dp0 set var=%var:~,-1% @echo "regi......

默克鱼
57分钟前
1
0
c++中友元函数理解与使用

在学习c++这一块,关于友元函数和友元类,感觉还是不好理解,但是井下心来,理解,需要把我一下几点。 首先讲友元函数。 (1)友元函数: 1)C++中引入友元函数,是为在该类中提供一个对外(除...

天王盖地虎626
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部