题解 | #装箱问题#

装箱问题

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背包问题稍作修改就可以得出这题的解答#
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务