旅行社建设网站,网页开发定制,宁阳县网络seo,怎么做网页版手机版网站题目描述
有一个箱子容量为v(正整数#xff0c;o≤v≤20000)#xff0c;同时有n个物品(o≤n≤30)#xff0c;每个物品有一个体积 (正整数)。要求从 n 个物品中#xff0c;任取若干个装入箱内#xff0c;使箱子的剩余空间为最小。
输入格式
第一行#xff0c;一个整…题目描述
有一个箱子容量为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 i0;in;i)//将箱子从大到小依次装到箱中{if(arr[i]sumv){sumarr[i];}}leftv-sum;//这里空间剩余3
for(int i0;in;i)
{if(arr[i]left)//以剩余空间作为判断条件 { sumarr[i];leftv-sum;//更新left}
}
最终代码得
#includestdio.hint main()
{int v, n;//v表示体积n表示物品个数int max, temp,sum0,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 j0;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 i0;in;i)//将箱子从大到小依次装到箱中{if(arr[i]sumv){sumarr[i];}}leftv-sum;//这里空间剩余3for(int i0;in;i){if(arr[i]left)//以剩余空间作为判断条件sumarr[i];leftv-sum;}printf(%d,left);return 0;
}
但这样写不具有通用性还是要用到动态规划算法代码如下
其中最重要的一段即 for(i1;in;i)
//从1开始是因为当v0, 箱子装不下任何东西i0表示第0件物品即没有物品所以跳过 for(jv;j1;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(jv;j1;j--) 还是不懂为什么j--
那么就多写
for(jv;j1;j--)的情况 for(j1;jv;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]后的容量大小不理解的可以依据上图观察规律 最终代码如下
#includestdio.hint w[40]{0};//注意初始化 ,这里表示物品的体积
int a[30011]{0};//这里表示v
int MAX(int n,int m)
{if(mn) return n;else return m;
}
int main()
{int n,i,j,v;scanf(%d,v); scanf(%d,n); for(i1;in;i)scanf(%d,w[i]);for(i1;in;i)//从1开始是因为当v0, 箱子装不下任何东西i0表示第0件物品即没有物品所以跳过 for(jv;j1;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]) 这是最简单的背包问题一定要理解如果还有点迷糊的话可以看看这篇文章
http://t.csdn.cn/X7GLD
或者
http://t.csdn.cn/CleVM
