题目描述
有一个箱子容量为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])
这是最简单的背包问题,一定要理解,如果还有点迷糊的话,可以看看这篇文章