洛灵酱的小窝

【算法学习】背包问题

RainbowBird
算法竞赛-笔记

发布于：Sep 4, 2020

字数：273字

时长：1分钟

次浏览

0  

今天好像终于搞懂了01背包问题。

先放上代码，过程以后再补。

01背包

朴素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int T, m;
int w[105], v[105];
int f[105][105];

int main() {
    cin >> T >> m;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= m; i++)
        cin >> w[i] >> v[i];

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

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

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int T, m;
int w[105], v[105];
int f[105];

int main() {
    cin >> T >> m;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= m; i++)
        cin >> w[i] >> v[i];

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

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

完全背包

完全背包相当于01背包只需要改动一句即可。

1
for (int j = T; j >= 0; j--)

改为

1
for (int j = 0; j <= T; j++)

本文作者：RainbowBird

本文链接：https://blog.luoling8192.top/posts/algorithm-note/knapsack.html

版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

更新于：Sep 5, 2020

动态规划

背包

01背包

完全背包

评论