装箱问题(背包问题)

简介: 装箱问题(背包问题)

题目描述

有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积  (正整数)。要求从  n  个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。


输入格式

第一行,一个整数,表示箱子容量;  第二行,一个整数,表示有n个物品;  接下来n行,分别表示这n个物品的各自体积。


输出格式

一个整数,表示箱子剩余空间。


样例输入

24

6

8

3

12

7

9

7

样例输出

0

解题思路


这一题乍一看与背包问题相似,但是相较于背包问题更加简单,没有价值设定,一开始我试着用更加通俗易懂的方法写,即从大到小依次遍历,进行装箱,直到装不下为止


我用了两个for循环以求left(剩余空间大小),即


//第一个for循环遍历到 装入下一个箱子,空间为负为止
for(int i=0;i<n;i++)//将箱子从大到小依次装到箱中
    {
        if(arr[i]+sum<v)
        {
            sum+=arr[i];
        }
    }
    left=v-sum;//这里空间剩余:3
for(int i=0;i<n;i++)
{
    if(arr[i]<=left)//以剩余空间作为判断条件    
    {         
        sum+=arr[i];
        left=v-sum;//更新left
    }
}


最终代码得


#include<stdio.h>
int main()
{
    int v, n;//v表示体积,n表示物品个数
    int max, temp,sum=0,left;
    scanf("%d", &v);
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    for (int i = 0; i < n; i++)//冒泡排序,将体积从大到小放入arr[i]中
    {
        for(int j=0;j < n-1-i;j++)
        {
            if (arr[j + 1] > arr[j])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
/*
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
*/
    for(int i=0;i<n;i++)//将箱子从大到小依次装到箱中
    {
        if(arr[i]+sum<v)
        {
            sum+=arr[i];
        }
    }
    left=v-sum;//这里空间剩余:3
    for(int i=0;i<n;i++)
    {
        if(arr[i]<=left)//以剩余空间作为判断条件
            sum+=arr[i];
            left=v-sum;
    }
    printf("%d",left);
    return 0;
}


但这样写不具有通用性,还是要用到动态规划算法,代码如下


其中最重要的一段即


for(i=1;i<=n;i++)
//从1开始是因为当v=0, 箱子装不下任何东西,i=0表示第0件物品,即没有物品,所以跳过 
        for(j=v;j>=1;j--)
/*
把数组压缩到一维必须逆序,因为01背包问题就是由旧值推新值,从前面开始的话,旧值就会过早被新值覆盖 
例如:
如果a[30]在a[20]的基础上加了w[i]=10,表示30容量这个背包它拿了w[i]=10这个东西了,但是--它没有考虑:a[20]里面是否拿过w[i]=10这个东西,所以要j--;
也就是说箱子的体积从小到大遍历,物品从大到小开始装,这样才能避免重复装入物品
*/
        {//j可以看作箱子当前的容量 
            if(w[i]<=j)//判断是否能装下物品i 
                a[j]=MAX(a[j],a[j-w[i]]+w[i]);//原式为a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) 
        }

for(j=v;j>=1;j--)


还是不懂为什么j--


那么就多写:


for(j=v;j>=1;j--)的情况



for(j=1;j<=v;j++)的情况



可以看到从a[14]开始,旧值已经覆盖新值了


注:a[j]为没放入,a[j-w[i]]+w[i]为放入

如下图所示a[j]为V(容量),a[j-w[i]]为放入w[i]后剩余的容量,a[j-w[i]]+w[i]为放入w[i]后的容量大小,不理解的可以依据上图观察规律:



最终代码如下


#include<stdio.h>
int w[40]={0};//注意初始化 ,这里表示物品的体积
int a[30011]={0};//这里表示v
int MAX(int n,int m)
{
    if(m<=n) 
        return n;
    else 
        return m;
}
int main()
{
    int n,i,j,v;
    scanf("%d",&v); 
    scanf("%d",&n); 
    for(i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(i=1;i<=n;i++)//从1开始是因为当v=0, 箱子装不下任何东西,i=0表示第0件物品,即没有物品,所以跳过 
        for(j=v;j>=1;j--)
/*
把数组压缩到一维必须逆序,因为01背包问题就是由旧值推新值,从前面开始的话,旧值就会过早被新值覆盖 
例如:
如果a[30]在a[20]的基础上加了w[i]=10,表示30容量这个背包它拿了w[i]=10这个东西了,但是--它没有考虑:a[20]里面是否拿过w[i]=10这个东西,所以要j--;
也就是说箱子的体积从小到大遍历,物品从大到小开始装,这样才能避免重复装入物品
*/
        {//j可以看作箱子当前的容量 
            if(w[i]<=j)//判断是否能装下物品i 
                a[j]=MAX(a[j],a[j-w[i]]+w[i]);//原式为a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) 
        }// a[j]为不拿,a[j-w[i]]+w[i]为拿
         //a[j-w[i]]+w[i]意为放入物品i后,总占用空间=物品i所占的空间+箱子剩余的空间 j-w[i] 所能被占用的最大空间 a[j-w[i]]
    printf("%d",v-a[v]);//此时的a[v]表示当容量为v时,箱子已被占用空间a[v] 
    return 0;
}


这是@佳佳佳佳佳博主的图,有助于理解


MAX(a[i-1][j],a[i-1][j-w[i]]+w[i])



这是最简单的背包问题,一定要理解,如果还有点迷糊的话,可以看看这篇文章


目录
相关文章
|
3月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
145 2
动态规划算法学习三:0-1背包问题
|
3月前
|
存储 算法
算法之背包问题
本文讨论了可分背包问题和0-1背包问题的区别及解决方法,其中可分背包问题可以使用贪心算法解决,而0-1背包问题则通常采用动态规划方法来找到最大价值的解决方案。
57 0
算法之背包问题
|
7月前
|
C++
每日练习之——背包问题
每日练习之——背包问题
37 1
|
8月前
|
算法 测试技术 C#
【动态规划法】0-1背包问题
【动态规划法】0-1背包问题
176 0
【33. 0 1 背包问题】
背包问题 - 一共有N件物品,背包容量为V,物品有俩个属性,一个是体积一个是价值(类似在一个宝岛上,你有一个背包,它只能装满这个背包,小岛上有很多金子,各种体积的,而且每个金子纯度不一样,看最后怎么装才会使得背包中的金子价值最高) **四种背包问题** - 0 1 背包 每件物品最多只用一次, - 完全背包 每件物品有无线个 - 多重背包 每个物品不一样,每个物品最多有有S<sub>i</sub>个——朴素版和优化版 - 分组背包 有水果,汽车,人等,每一种里面最多只能选择一个
167 0
【33. 0 1 背包问题】
|
算法 大数据
背包问题(一)
复习acwing算法基础课的内容,本篇为讲解基础算法:动态规划——背包问题,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
132 0
背包问题(一)