文档章节

背包问题

a_xianyu
 a_xianyu
发布于 2017/09/04 14:42
字数 1112
阅读 18
收藏 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
哈尔滨
程序员
私信 提问
加载中
请先登录后再评论。

暂无文章

倒计时一周,HOLOS千人大会即将召开!

8月10日消息,Holos霍洛斯星际云自由能源将于2020年8月17日在深圳召开千人媒体发布会。据了解,此次发布会将请到众多行业领袖、区块链技术精英、数十位国家级专科院士以及多位能源行业重量级...

osc_njd5t1rw
47分钟前
17
0
Goroutine 泄露排查

我们在发布一个 go 应用时,默认都会启用两个 http handler: 一个是 pprof,方便线上动态追踪问题;另外一个是 prometheus 的 metrics,这样就可以通过 grafana 准实时的监控当前 runtime 信...

ms2008
2019/06/03
6
0
如何在Python中打印到stderr? - How to print to stderr in Python?

问题: There are several ways to write to stderr: 有几种写stderr的方法: # Note: this first one does not work in Python 3print >> sys.stderr, "spam"sys.stderr.write("spam\n")......

法国红酒甜
49分钟前
27
0
关于JWT Token 自动续期的解决方案

前言 在前后端分离的开发模式下,前端用户登录成功后后端服务会给用户颁发一个jwt token。前端(如vue)在接收到jwt token后会将token存储到LocalStorage中。 后续每次请求都会将此token放在请...

飘渺Jam
07/16
20
0
5G时代会不会导致编程语言大灭绝,JS的前景是否会更好-诺禾

首先,5G打开了工业互联网的大门,同时5G也会推动一系列技术的发展,包括物联网、大数据、边缘计算、人工智能等等,而这些技术的发展又会推动各种技术平台的发展,从而形成以技术平台为基础来...

osc_jo2m8l1r
49分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部