currently reading articles under 算法

《背包九讲》笔记

背包问题

题意:给出背包的容量,以及一批物品的价值和大小,求最大价值。

01背包问题

题意

每个物品只能放入一次。

思路

用f[i][v]表示,第i个大小为v的物品放入时的总价值。

c[i]表示第i个物品的价值。w[i]为第i个物品的大小。

状态转移方程:f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+c[i]);

状态转移方程表示,取放入或者不放入第i个物品两种情况的最大值。

空间优化(滚动数组)

初始状态方程的空间复杂度是O(V*W),可以进一步优化。

可以将空间优化为O(2*W),即纵向大小为2。

for(i=1; i<=N; i++......

Javax.swing学习记录

待更新

概述

在Java初期,包含了一个用于基本GUI程序设计的类库,称为AWT (Abstract Window Toolkit)。基本AWT库采用将处理用户界面元素的任务为派给每个目标平台的本地GUI工具箱的方式,由本地工具箱负责用户界面元素的创建和动作。

问题在于,虽然可以运行与多平台,但是不同平台的观感却很难统一。更坏的是,不同平台上的AWT用户界面库中存在着不同的bug,因而在每个平台上都必须测试应用程序。

后来,创建了IFC库,通过在空白窗口上绘制用户界面元素来统一在不同平台上的外观和动作。后来,经过合作完善,发展成了现在的Swing库。

现在,Swing是指“被绘制的”用户界......

Python Scraping学习记录

待更新

安装BeautifulSoup4

Linux

$sudo apt-get install python-bs4

macOS

$sudo easy_install pip

$pip3 install beautifulsoup4

导入

from bs4 import BeautifulSoup

尝试运行

from urllib.request import urlopen

from bs4 import BeautifulSoup

html = urlopen("http://www.pythonscraping.com/pages/page1.html&quo......

搜索专题整理

A - 棋盘问题 (POJ 1321)

题意

在一个n*n的棋盘上放置k个棋子,棋子不能同行同列。求方法数。

思路分析

DFS递推。

搜索当前行,每找到一个棋盘位置就递归到下一行搜索。

当前行搜索完毕之后就搜索下一行。

代码

#include<cstdio>

using namespace std;

char map[8][8];

int n, k, cnt, now; // 记录总方案数和当前已经放置的棋子数目。

int vis[8]={0};

void dfs(int cur){

if(k == now){ cnt++; return; }

if(......

Android学习记录

待更新

LogCat

Android Studio中已经默认添加了LogCat工具,macOS使用control+6,Win使用Alt+6打开。

Android中的日志工具类是Log(android.util.Log),这个类中提供了如下方法:

Log.v() //这个方法打印最为琐碎的,意义最小的日志信息,对应级别verbose

Log.d() //这个方法打印一些调试信息,对应级别debug

Log.i() //这个方法打印一些警告,提示程序的潜在风险,对应级别warn

Log.e() //这个方法用于打印错误信息,对应级别error

尝试

在onCreate()方法中添加一行打......