算法训练 装箱问题 蓝桥杯

目录

装箱问题  

问题描述

 思路

代码实现

装箱问题  

时间限制：1.0s   内存限制：256.0MB

问题描述

　有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

　　第一行为一个整数，表示箱子容量；

　　第二行为一个整数，表示有n个物品；

　　接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

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

样例输入

　　24

　　6

　　8

　　3

　　12

　　7

　　9

　　7

样例输出

 思路

此题是背包型的动态规划，物品价值等于物品自身的体积。v[i][j]表示前i件物品放入容量j的背包获得的最大价值 (此题最大价值就是容量)，若w[i]大于容量j,则v[i][j]=v[i-1][j]；若w[i]小于等于容量j,则v[i][j]=max(v[i-1][j], v[i-1][j-w[i]]+w[i])。本人所写代码适用于一般的背包问题 ，只需添加回溯过程即可找到放入背包的物品，由于此题不需要这一过程，因此代码可以继续优化，详情请参考https://blog.csdn.net/qq_18860653/article/details/53260949

代码实现

#include<iostream>
using namespace std;
	//v[i][j]表示前i件物品放入容量j的背包获得的最大价值 (此题最大价值就是体积)
main(){
	int C,n;
	cin >> C >> n;        //C表示最大容量
	int v[n+1][C+1],w[n+1];
	int temp;
	for(int i=1;i<=n;i++){
		cin >> temp;
		w[i]=temp;
	}
	for(int i=1;i<=n;i++)
	    v[i][0]=0;
	for(int j=1;j<=C;j++)
	    v[0][j]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=C;j++){
			if(w[i]>j)
			   v[i][j]=v[i-1][j];
			else
			   v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+w[i]);
		}
	} 
	cout << C-v[n][C] << endl;
	return 0;
}