d862 - NOIP2001 4.装箱问题

🔗 前往 ZeroJudge 原題

題目描述

題目要求給定一個箱子容量 V 和 n 個物品的體積，找到一種物品的組合，使得箱子的剩餘空間最小。

解題思路

這題可以視為一個背包問題的變形。目標不是最大化裝入的物品總體積，而是最小化剩餘空間。程式碼的思路是嘗試將物品放入箱子，並記錄每個可能剩餘空間的出現次數。由於題目限制物品數量較少，因此可以採用一種類似動態規劃或回溯的策略，但程式碼實現上更像是貪心策略的嘗試。程式碼遍歷所有可能的物品組合，並計算對應的剩餘空間。它使用一個陣列 b 來記錄每個剩餘空間值出現的次數。最後，程式碼找到第一個非零的 b 陣列索引，該索引表示最小的剩餘空間。

複雜度分析

• 時間複雜度: O(2^n * V) (最壞情況下，需要遍歷所有 2^n 個物品子集，並且對於每個子集，需要計算剩餘空間，這可能需要 O(V) 的時間)
• 空間複雜度: O(V) (使用一個大小為 V 的陣列 b 來儲存剩餘空間的出現次數)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a;
	cin >> a;
	int b[a+1]={0},c,d;
	cin >> c;
	while(c--){
		cin >> d;
		for(int i=0;i<=a;i++)
			if((b[i]!=0&&i-d>=0)||i==a)
				b[i-d]++;
	}
	for(int i=0;i<=a;i++){
		if(b[i]!=0){
			cout << i << '\n';
			break;
		}
	}
}