A+B

A+B

1
2
3
4
5
6
7
8
9
10
11
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner cin=new Scanner(System.in);
        int a = cin.nextInt();
        int b = cin.nextInt();
        System.out.println(a + b);
    }
}
1
2
a,b=map(int,input().split())
print(a+b)

map函数，Python内置函数，映射函数

语法

1
2
3
map(function,iterable)
# function -- 函数
# iterable -- 序列
  1. 列表做参
    1
    2
    >>> list(map(int,[2.34,13.14,66]))
    [2,13,66]
  2. 自定义函数做参
    1
    2
    3
    4
    def my(x):
        return x+1
    print(tuple(map(my,{2,3.6,6})))
    # (3,4.6,7)
  3. map函数返回的是一个map类型的序列，而不是列表
    1
    2
    >>> type(map(int,[3,4]))
    <class 'map'>
  4. 当function函数没有返回值的时候，返回一个由None组成的序列
    1
    2
    3
    4
    def my(number):
        pass
    print(list(map(my,[1,2,3])))
    #[None,None,None]

01背包问题

假设你是个小偷，背着一个可以装4磅东西的背包。
可偷窃的商品入下：
可偷窃的东西
为了让偷窃的商品价值最高就是01背包问题
枚举法在商品多到一定程度的时候肯定是行不通的，如何找到最优解呢？答案是使用动态规划

动态规划


对于背包问题，先解决小背包（子背包）问题，再逐步解决原来的问题。
先解决小背包问题
每个动态规划算法都从一个网格开始
吉他行
只有吉他可供选择
音响行
可偷的商品有吉他和音响
更新了最大值
笔记本电脑行
3磅的背包，选择偷窃价值2000美元的笔记本电脑而不是吉他
4磅背包
最终答案

公式


单元格公式

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int V = cin.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            v[i] = cin.nextInt();
            w[i] = cin.nextInt();
        }
        int[][] cell = new int[N + 1][V + 1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < V + 1; j++) {
                if (j >= v[i]) {
                    cell[i][j] = Math.max(cell[i - 1][j - v[i]] + w[i], cell[i - 1][j]);
                } else {
                    cell[i][j] = cell[i - 1][j];
                }
            }
        }
        System.out.println(cell[N][V]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
N,V=list(map(int,input().split()))
things=[[0]*2 for i in range(N+1)]
for i in range(1,N+1):
    things[i][0],things[i][1]=list(map(int,input().split()))
cell=[[0]*(V+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,V+1):
        #j空间大的背包，j大于物品体积的时候才有剩余空间价值
        if(j>=things[i][0]):
            if(cell[i-1][j]>things[i][1]+cell[i-1][j-things[i][0]]):
               cell[i][j]=cell[i-1][j]
            else:
                cell[i][j]=things[i][1]+cell[i-1][j-things[i][0]]
        else:
            cell[i][j]=cell[i-1][j]
print(cell[N][V])

python定义二维数组

使用numpy 

1
2
3
4
5
6
7
8
9
import numpy as np
arr=[[0]*3 for i in range(3)]
arr1=np.zeros([3,3])
print(arr1)
'''
[[0. 0. 0.]
 [0. 0. 0.]
 [0. 0. 0.]]
'''
使用for循环 
1
2
3
arr=[[0]*3 for i in range(3)]
print(arr)
#[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

完全背包问题

结合01背包问题图解我们得到了01背包问题的递推式子
完全背包问题就是物品数量无限，其实也可以强行01背包问题求解$cell[i][j]$

  • $v[i]$表示物品体积
  • $w[i]$表示物品价值
  • 不选第i种物品：$cell[i-1][j]$
  • 选1个第i种物品：$cell[i-1][j-v[i]]+w[i]$
  • 选2个第i种物品：$cell[i-1][j-2v[i]]+2w[i]$
  • 因为过程有限，过程不能无限下去，对于第i个物品，最多可以装$\frac{j}{v[i]}$个
  • 所以递推式子其实就是

到这一步，已经能写出代码了，见python，只不过时间复杂度太大了，运行不通过

继续往下分析

等式两边同时加上$w[i]$

仔细看③与①相比就少了$cell[i-1][j]$,于是有了完全背包递推公式如下：

完全背包

未优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
N,V=list(map(int,input().split()))
v=[0]*(N+1)
w=[0]*(N+1)
for i in range(1,N+1):
    v[i],w[i]=list(map(int,input().split()))
cell=[[0]*(V+1) for i in range(N+1)]
def findMax(i,j):
    max=cell[i-1][j]
    for k in range(int(j/v[i]+1)):   
        if(cell[i-1][j-k*v[i]]+k*w[i]>max):
            max=cell[i-1][j-k*v[i]]+k*w[i]
    return max
for i in range(1,N+1):
    for j in range(1,V+1):
       cell[i][j]=findMax(i,j)
print(cell[N][V])
优化
1
2
3
4
5
6
7
8
9
10
for i in range(1,N+1):
    for j in range(1,V+1):
        if(j>=v[i]):
            if(cell[i][j-v[i]]+w[i]>cell[i-1][j]):
                cell[i][j]=cell[i][j-v[i]]+w[i]
            else:
                cell[i][j]=cell[i-1][j]
        else:
            cell[i][j]=cell[i-1][j]
print(cell[N][V])

多重背包

如果$s[i]v[i]>V$，不就是一个完全背包
所以多重背包问题就是要转换成01背包+完全背包