算法訓練 裝箱問題 藍橋杯

目錄

裝箱問題  

問題描述

 思路

代碼實作

裝箱問題  

時間限制：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;
}