动态规划基础 ——装箱问题

2024-01-09 18:24:50

题目描述

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

输入格式

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

样例

24
6
8
3
12
7
9
7
0

我的代码

#include <bits/stdc++.h>
using namespace std;
int v[20001]={0};
void findlarge(int m,int n,int a[])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i];j--)
        {
            if(v[j]>v[j-a[i]]+a[i])
            {
                v[j]=v[j];
            }
            else
                v[j]=v[j-a[i]]+a[i];
        }
    }
    cout<<m-v[m]<<endl;
}
int main()
{
    int i,m,n,a[35]={0};
    cin>>m>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    findlarge(m,n,a);
    return 0;
}

?我的解题思路:

作为一个新手,我并不清楚什么是动态规划,但因为学过一些离散数学的知识,简单理解的话,其实动态规划和递推方程之间有点联系

在下面这个博主的博客里面详细的介绍了递归与递推的区别,从某种意义上讲,个人感觉动态规划可以算作是递归算法的优化,它将已经算好的数据存储在数组里,避免了递归造成的重复计算,大大减少了时间开销

教你彻底学会动态规划——入门篇-CSDN博客

(有的算法是逐步优化成这个样子的,所以可以先去学习了解一下最初时算法的样子,这样可以更方便理解)

对于本题而言,因为并不能单纯的选择较大或者较小的数,来填满箱子,于此同时,我们并不清楚最佳方案时的个数,所以很难通过暴力枚举的算法来解决

于是,我们可以简要的学习一下本题所用的动态规划的思路:

首先,设个数组,来数组的下标代表每一种空间容量,也就是从1~最大值,

然后,我们开始将物品逐个放入,在不超过背包空间容量的前提下,取最大值。

最后,做减法即可。

如果你好奇整个数组是如何变化的。

那么我们不妨尝试着把该数组输出一下:

结果如下:

14
4
3
7
5
8
1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10 ? ?11 ? ?12 ? ?13 ? ?14
0 ? ? 0 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 3
0 ? ? 0 ? ? 3 ? ? 3 ? ? 3 ? ? 3 ? ? 7 ? ? 7 ? ? 7 ? ? 10 ? ?10 ? ?10 ? ?10 ? ?10
0 ? ? 0 ? ? 3 ? ? 3 ? ? 5 ? ? 5 ? ? 7 ? ? 8 ? ? 8 ? ? 10 ? ?10 ? ?12 ? ?12 ? ?12
0 ? ? 0 ? ? 3 ? ? 3 ? ? 5 ? ? 5 ? ? 7 ? ? 8 ? ? 8 ? ? 10 ? ?11 ? ?12 ? ?13 ? ?13

我们发现,对于任意v,v[i]均小于v

参考资料

1.

C语言算法训练 - 装箱问题_动态规划问题(有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数))_有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积-CSDN博客

?2.

教你彻底学会动态规划——入门篇-CSDN博客

文章来源:https://blog.csdn.net/qq_74854522/article/details/135466278
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。