acwing

A+B

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 2	>>> list(map(int,[2.34,13.14,66])) [2,13,66]

自定义函数做参

def my(x):
    return x+1
print(tuple(map(my,{2,3.6,6})))
# (3,4.6,7)

map函数返回的是一个map类型的序列，而不是列表
1
2
>>> type(map(int,[3,4]))
<class 'map'>
当function函数没有返回值的时候，返回一个由None组成的序列
1
2
3
4
def my(number):
pass
print(list(map(my,[1,2,3])))
#[None,None,None]

01背包问题

假设你是个小偷，背着一个可以装4磅东西的背包。
可偷窃的商品入下：

为了让偷窃的商品价值最高就是01背包问题
枚举法在商品多到一定程度的时候肯定是行不通的，如何找到最优解呢？答案是使用动态规划

动态规划

对于背包问题，先解决小背包（子背包）问题，再逐步解决原来的问题。

吉他行

音响行

笔记本电脑行

公式

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]);
    }
}

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

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]}$个
所以递推式子其实就是

$cell[i][j]=max_{ (0{\leq}k{\leq}t)}(cell[i-1][j],cell[i-1][j-kv[i]]+kw[i])$

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

继续往下分析

$cell[i][j]=max_{ (0{\leq}k{\leq}t)}(cell[i-1][j],cell[i-1][j-v[i]]+w[i],cell[i-1][j-2v[i]]+2w[i],...)①$ $cell[i][j-v[i]]=max_{ (0{\leq}k{\leq}t)}(cell[i-1][j-v[i]],cell[i-1][j-v[i]-v[i]]+w[i],...)②$

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

$cell[i][j-v[i]]+w[i]=max_{ (0{\leq}k{\leq}t)}(cell[i-1][j-v[i]]+w[i],cell[i-1][j-v[i]-v[i]]+w[i]+w[i],...)③$

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

$cell[i][j]=max(cell[i][j-v[i]]+w[i],cell[i-1][j])$

未优化

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])

优化

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])