背包问题 🎒

发表评论

九种背包问题

01背包问题

一种物品只能放入背包或者不放入，不可分割，只考虑物品体积不考虑物品质量，体积有限的背包如何携带价值做多的物品

AcWing题目地址

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/**
 * f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
 * 1. 不选第i个物品 f[i][j] = f[i-1][j]
 * 2. 选第i个物品 f[i][j] = f[i-1][j-volume[i]] + value[i] 
 * f[i][j] = max(1,2);
 * f[0][0] = 0;
 */
int bag(int *volumes, int *values, int capacity);

int main(const int argc, const char **argv) {
    int size, capacity;
    while (scanf("%d %d",&size,&capacity)!=EOF) {
        /**
         * 数组第一个元素保存数组长度
         */
        int *volumes = (int *) calloc(size+1, sizeof(int));
        int *values = (int *) calloc(size+1, sizeof(int));
        values[0] = volumes[0] = size;
        for (int i=1;i<=size;i++) scanf("%d %d",volumes+i,values+i);
        int ret = bag(volumes,values,capacity);
        printf("%d\n",ret);
        free(volumes);
        free(values);
    }
    return 0;
}

int bag(int *volumes, int *values, int capacity) {
    int length = volumes[0];
    int **bags = (int **) calloc(length+1, sizeof(int *));
    for (int i=0;i<=length;i++) bags[i] = (int *) calloc(capacity+1, sizeof(int));
    bags[0][0] = 0;
    for (int i=1;i<=length;i++) {
        for (int j=0;j<=capacity;j++) {
            /**
             * 第i个物品是否放入背包，如果不放入背包
             */
            bags[i][j] = bags[i-1][j];
            /**
             * 第i个物品体积小于背包剩余体积，才能放入背包
             */
            if (j>=volumes[i]) 
                bags[i][j] = fmax(bags[i][j],bags[i-1][j-volumes[i]]+values[i]);
        }
    }
    int ret = 0;
    for (int i=0;i<=capacity;i++) ret = fmax(bags[length][i],ret);
    for (int i=0;i<length;i++) free(bags[i]);
    free(bags);
    return ret;
}

继续阅读 →

JAVA基础 🔪

发表评论

JDBC连接数据库

public class JDBCTest {
    public static void main(String[] args) {
        String url = "jdbc:sqlserver://db.host.com;database=education";
        String username = "SA";
        String password = "PassWord";
        Connection conn = null;
        try {
            conn = DriverManager.getConnection(url,username,password);
            Statement sql = conn.createStatement();
            ResultSet result = sql.executeQuery("select * from users");
            while (result.next()) {
                var id = result.getInt(1);
                var name = result.getString(2);
                var pass = result.getString(3);
                System.out.println(id + "\t" + name + "\t" + pass);
            }
        } catch (SQLException throwable) {
            throwable.printStackTrace();
        }
    }
}

继续阅读 →

iOS固件提取资源 ⛲️

发表评论

最近在制作字体模块，需要提取iOS14内置的一些资源

首先用BetterZip打开下载的iOS固件，iOS固件可以在这个网站上面下载

打开以后，选择最大的dmg文件，右键将其挂在到Finder

像这样

等待解压完毕，挂载成功，就可以在Finder中看到这个分区文件了，和访问手机根目录结构一样

原神，终于来了 🐨

发表评论

来了，来了!

继续阅读 →

直播 👗

1条回复

SRS

服务器用的是apache, apache在直播中用的没有nginx多，再安装一个web服务器功能就有些重叠了，所有这里用SRS来搭建直播流服务。采用docker镜像安装

首先安装podman(RHEL8)自带

podman run -p 1935:1935 -p 1985:1985 -p 8080:8080 ossrs/srs:3

启动后是这样的。

file

接下来就是放行1935端口，这里添加一个配置文件.

<?xml version="1.0" encoding="utf-8"?>
<service>
  <short>RTMP</short>
  <description>Real-Time Messaging Protocol.</description>
  <port port="1935" protocol="tcp"/>
  <port port="1935" protocol="udp"/>
</service>

把这个文件名为为rtmp.xml放到/etc/firewalld/services，然后是用firewall-cmd --permanent --add-service=rtmp启用配置，然后使用firewall-cmd --reload重载服务即可

推流

使用ffmpeg推流，比如我服务器绑定了域名vps.ourfor.top, 推流命令就是

ffmpeg -re -i 海贼王08主题曲.m4v \
-vcodec copy -acodec copy \
-f flv -y rtmp://vps.ourfor.top/live/livestream # 域名以后的部分随意填写

使用IINA播放地址rtmp://vps.ourfor.top/live/livestream即可

直播

直播的话，使用ffmpeg采集屏幕画面或者摄像头画面推流即可

继续阅读 →