头像

算法小白

Acwing大学,学号:67143 (我很菜 别骂了 别骂了T.T)




离线:8小时前


最近来访(114)
用户头像
修勾啊
用户头像
忆--世界
用户头像
OIerty
用户头像
yangbing
用户头像
冰之韵
用户头像
林小鹿
用户头像
V1
用户头像
图灵机
用户头像
xiayutao
用户头像
用户头像
Assert
用户头像
Makisekurisu_4
用户头像
no_one
用户头像
价值2千的胡歌
用户头像
TEN.X
用户头像
楚天
用户头像
gAg
用户头像
Expelliarmus2011
用户头像
封禁用户
用户头像
芒果黄桃冰

活动打卡代码 AcWing 3. 完全背包问题

朴素算法(TLE)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j <= m; j ++)
        {
            for(int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

二维优化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) 
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

一维优化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++)
    {
        for (int j = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

算法小白
2个月前

二维数组(朴素算法)

// 二维枚举(曲线救国doge)
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N]; // v[N]表示物品体积,w[N]表示物品价值
int f[N][N]; // 二维数组f[N][N]表示物品价值总和

int main()
{
    cin >> n >> m; // 输入物品数量和背包容积

    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; // 输入每一个物品的体积和价值

    // 注意f[0][0~m] = 0,价值总和最大应该在f[n][0~m]
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j <= m; j ++)
        {
            // 注意不包含i的情况一定存在
            // 故而先将前i-1个物品总价值先赋值给包含第i件物品的情况,进而继续讨论
            f[i][j] = f[i - 1][j];

            // 而包含i的情况不一定存在,只有在j >= v[i],即体积j大于等于当前第i个物品的体积时
            // 在 前i-1个物品 与 包含第i件物品 中选择最大价值总和
            if (j >= v[i]) 
                // 牢记状态转方程
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    // 输出前n件物品中 体积不超过m的 最大价值总和
    cout << f[n][m] << endl;

    return 0;
}

一维数组(空间优化)

// 一维数组(优化空间)
/*
可优化原因:
1. f[i] 这一层只用到了f[i - 1] 这一层 ==> 滚动数组(交替出现)
2. j 和 j - v[i] 都严格小于或等于 j,不存在在j的两侧
*/
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N]; // v[i]表示第i个物品的体积 w[i]表示第i个物品的价值
int f[N]; //一维数组f[N]表示价值总和

int main()
{
    // 输入物品数量和背包容积
    cin >> n >> m; 
    // 输入每一个物品的体积和价值
    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    // 顺序输出
    // for(int i = 1; i <= n; i ++)
    // {
    //     for (int j = v[i]; j <= m; j ++)
    //     {
    //         f[j] = max(f[j], f[j - v[i]] + w[i]);  
    //         f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i])
    //     }
    // }

    /*
    分析如下:
        1. j - v[i] 严格小于 j
        2. j 递增
        3. j - v[i] 一定比 j 先更新
        4. 故而f[j - v[i]] 在第i层已经被更新过,但是我们需要的是i-1层,故而有错
    */

    // 逆序输出 保证每次用到的都是第i-1层的数据,即j-v[i]在此时i层未被修改过
    for (int i = 1; i <= n; i ++)
    {
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }

    cout << f[m] << endl;
    return 0;
}


活动打卡代码 工程课 Linux-1.9. homework_9

算法小白
2个月前
cd /home/acs/homework/lesson_1/homework_9
rm *.txt


活动打卡代码 工程课 Linux-1.8. homework_8

算法小白
2个月前
cd /home/acs/homework/lesson_1/homework_8
cd dir_a
rm a.txt
cd ..
cd dir_b
mv b.txt b_new.txt
cd ..
cd dir_c
cp c.txt c.txt.bak


活动打卡代码 工程课 Linux-1.7. homework_7

算法小白
2个月前
cd ..
cd homework_7
cp a.txt dir_0/a0.txt
cp b.txt dir_0/b0.txt
cp c.txt dir_0/c0.txt
cp a.txt dir_1/a1.txt
cp b.txt dir_1/b1.txt
cp c.txt dir_1/c1.txt
cp a.txt dir_2/a2.txt
cp b.txt dir_2/b2.txt
cp c.txt dir_2/c2.txt


活动打卡代码 工程课 Linux-1.6. homework_6

算法小白
2个月前
cd ..
cd homework_6
cat task.txt
mv task.txt done.txt
mkdir dir_a
mv done.txt dir_a


活动打卡代码 工程课 Linux-1.5. homework_5

算法小白
2个月前
cd ..
cd homework_5
rm dir_a dir_b dir_c -r


活动打卡代码 工程课 Linux-1.4. homework_4

算法小白
2个月前
cd ..
cd homework_4
rm a.txt b.txt c.txt


活动打卡代码 工程课 Linux-1.2. homework_2

算法小白
2个月前
cd ..
cd homework_2
mv a.txt a_new.txt
mv b.txt b_new.txt
mv c.txt c_new.txt


活动打卡代码 工程课 Linux-1.3. homework_3

算法小白
2个月前
cd ..
cd homework_3
mv dir_a/a.txt dir_b/
mv dir_a/b.txt dir_b/
mv dir_a/c.txt dir_b/
(mv dir_a/* dir_b/)