《算法提高课》题解与笔记上线啦！(链接就是这个){: style=”color: #FF0000”}

创建时间2024-1-23

$$ #3 1024.装箱问题 $$

01背包模型

原题Link

DP Code:

# include <bits/stdc++.h>
using namespace std;

const int N = 40, M = 2e4 + 10;

int n, v;
int m[N], f[M];

int main(){
    scanf("%d %d", &v, &n);

    for(int i = 1; i <= n; i ++) scanf("%d", &m[i]);

    for(int i = 1; i <= n; i ++)
        for(int j = v; j >= m[i]; j --)
            f[j] = max(f[j], f[j - m[i]] + m[i]); // 体积是体积，也是价值，这一点很重要

    printf("%d", v - f[v]);

    return 0;
}

DFS Code:

# include <bits/stdc++.h>
using namespace std;

const int N = 30;

int n, v, ans;
int m[N];

void dfs(int k, int sum){
    if(sum > v) return;
    if(sum == v){
        printf("0");
        exit(0);
    }

    if(k == n + 1){
        ans = max(ans, sum);
        return;
    }

    dfs(k + 1, sum + m[k]);
    dfs(k + 1, sum);
}

int main(){
    scanf("%d %d", &v, &n);

    for(int i = 1; i <= n; i ++) scanf("%d", &m[i]);

    dfs(1, 0);

    printf("%d", v - ans);

    return 0;
}