文档章节

背包问题

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

暂无文章

CentOS 安装PHP5和PHP7

安装PHP5 下载解压二进制包 [root@test-a src]# cd /usr/local/src/[root@test-a src]# wget http://cn2.php.net/distributions/php-5.6.32.tar.bz2[root@test-a src]# tar jxvf php-5.6......

野雪球
今天
4
0
windows上类似dnsmasq的软件Dual DHCP DNS Server

官网地址:http://dhcp-dns-server.sourceforge.net/官网定向的下载地址:https://sourceforge.net/projects/dhcp-dns-server/files/ 设置参考地址:http://blog.51cto.com/zhukeqiang/18264......

xueyuse0012
今天
3
0
LinkedHashMap源码解析

前言 HashMap中的元素时无序的,也就是说遍历HashMap的时候,顺序和放入的顺序是不一样的。 如果需要有序的Map,就可以采用LinkedHashMap. LinkedHashMap通过维护一个包含所有元素的双向链表,...

grace_233
今天
3
0
初识flask

文档 0.10.1版本 http://www.pythondoc.com/flask/index.html 1.0.2版本 https://dormousehole.readthedocs.io/en/latest/ 安装flask $ pip3 install flaskCollecting flask Downloading......

yimingkeji
昨天
6
0
Akka系统《sixteen》译

Actor是一个封装状态(state)和行为(behavior)的对象,它们只通过交换消息通信(放入收件人邮箱的邮件)。从某种意义上说,Actor是最严格的面向对象编程形式,但它更适合将他们视为人:在与Act...

woshixin
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部