题解 | #装箱问题#
装箱问题
https://www.nowcoder.com/practice/c990bd0bf8e04bfbb19c0964401c8f77
该题可以视为01背包问题的变形。
题目求箱子的剩余空间为最小，即求V-箱子最大能装进去的物品体积和。
注意到装箱结束箱子内物品体积和小于V，可以将每个物品的体积视为价值，则改题转化为求最多能容纳的体积是V的背包中，至多能装多大价值的物品？（这里体积vi =价值wi）
最终结果为V-箱子最大能装进去的物品体积和。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int V;
cin >> V;
int n;
cin >> n;
vector<int> items(n);
for (int i = 0; i < n; i++) {
cin >> items[i];
}
vector<int> dp(V + 1, 0);
for (int i = 0; i < n; i++)
{
for (int j = V; j >= items[i]; j--) {
dp[j] = max(dp[j], dp[j - items[i]] + items[i]);
}
}
cout << V - dp[V] << endl;
}
#经典01背包问题稍作修改就可以得出这题的解答#
腾讯成长空间 5952人发布
