526互联

1024. 装箱问题

发布时间 2023-03-30 13:49:29作者: zhangk1988

题目描述

给了一个箱子的总体积是V，同时有n件物品，每件的都有一个体积，问怎么去可以让剩余空间最小？

f1-01背包-没有显式给价值

基本分析

  1. 剩余空间最小？占用的体积最大
  2. 01背包的价值是啥？也是v

代码

#include <iostream>

using namespace std;

const int N = 200010;
int f[N];

int m, n;

int main()
{
    scanf("%d%d", &m, &n);
    
    for (int i = 1; i <= n; i++)
    {   
        int v;
        scanf("%d", &v);
        for (int j = m; j >=v; j-- )
            f[j] = max(f[j], f[j-v]+v);
    }
    
    printf("%d\n", m - f[m]);
    
    return 0;
}

总结

  1. 定义dp状态的时候，N是第二个维度（体积）的上限，不是第一个维度