关于动态规划/性价比/背包问题的思考

01背包本质上就可以用空间换时间，动规本质上也是那空间换时间，本身也就是一个贪心算法，所以
01背包<–>贪心<–>动态规划

如果说是0-1背包问题，需要逆序更新，原因是东西只有一个，不能影响之前的部分

如果是东西有无数个，则直接顺序更新

如果东西是牛奶之类的，有性价比，并且可以买非整数数量的，可以退化为贪心来做，结构体：数量，价格，性价比，sort一下就完事儿了。

讲究序列（排列问题），先遍历背包，不要求序列（组合问题），先遍历物品

滚动数组

另外，0-1背包要求倒序，若要求组合而非排列，即为先物品，再背包，且倒顺序，滚动数组添加

而且，如果是算有多少种，直接加就行,dp[0]=1，其他为0

1
2
3
dp[j]+=dp[j-nums[i]]
    //这里怎么去理解呢，会导致重复吗？
    //不会重复

如果是要算最多/最少，还要min和max比较

1
dp[j]=max(dp[j],dp[j-nums[i]]+value[i])

[(425条消息) 背包问题（背包九讲）_你好世界wxx的博客-CSDN博客](https://blog.csdn.net/weixin_42638946/article/details/114028588?ops_request_misc=%7B%22request%5Fid%22%3A%22167933155516800186567314%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fall.%22%7D&request_id=167933155516800186567314&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~pc_rank_34-6-114028588-null-null.142^v74^pc_new_rank,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=01背包问题 凑整&spm=1018.2226.3001.4187)

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Created by WXX on 2021/2/24 14:36
#include <iostream>

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 = m; j >= v[i]; j--) //倒叙
            f[j] = max(f[j], f[j - v[i]] + w[i]);

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

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Created by WXX on 2021/2/24 15:21
#include <iostream>

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

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Created by WXX on 2021/2/24 16:07
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {

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

    for (int i = 1; i <= n; i++)  // 先循环物品
        for (int j = 0; j <= m; j++)  // 再循环容量
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)  // 最后循环决策
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[n][m] << endl;
    return 0;
}