分类目录归档:💅 · 生活

背包问题 🎒

九种背包问题

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

继续阅读

☃️ 越狱插件

Cydia常用软件源

A Sileo蜜蜂源™ 官网
壹筒天下官方源 官网
Cydiakk中文源™ 官网
DEB推送源™ 官网
Ant 蚂蚁源 官网

效果

继续阅读

Hello world! 🙄

这篇是WordPress自动生成的文章,很久没有用WordPress了,仪表盘还是原来的样子,安装完成后,从前安装的主题自动同步下来了,有种莫名的感动,希望初心依旧!

继续阅读

Doctor 异乡人 🐝

:emoji-b000b:Doctor Stranger(中译名:Doctor 异乡人)

男主朴勋(李钟硕饰), 小时候因为父亲朴哲前往朝鲜为当时的最高领导人金日成做手术而与女主李在熙(陈世妍饰)相识,女主的父亲犯了政治错误,女主被流放,之后又因种种变故与男主相遇的故事:emoji-d000e: 。

继续阅读

小米超神 🎮

虽然早就没有玩过 moba 游戏了,主要是没有什么时间玩,77 ,但是我还是比较期待英雄联盟手游75 ,下面 👇是我以前打游戏的视频,主要是为了测试博客的视频播放功能。以前博客里面放视频,我都是将视频存在自己的服务器,然后播放器也是自己定制的。现在打算使用第三方引流,提高观看体验

继续阅读