分类目录归档：💅 · 生活

背包问题 🎒

九种背包问题

01背包问题

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

#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;
}

继续阅读 →

挂载云盘 ☁️

发表评论

将云盘挂载为本地磁盘

rclone (不推荐，问题太多)
raidrive
netdrive
mountainduck

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

继续阅读 →