試題 算法訓(xùn)練 裝箱問題

資源限制

在成都網(wǎng)站建設(shè)、做網(wǎng)站過程中，需要針對(duì)客戶的行業(yè)特點(diǎn)、產(chǎn)品特性、目標(biāo)受眾和市場情況進(jìn)行定位分析，以確定網(wǎng)站的風(fēng)格、色彩、版式、交互等方面的設(shè)計(jì)方向。創(chuàng)新互聯(lián)還需要根據(jù)客戶的需求進(jìn)行功能模塊的開發(fā)和設(shè)計(jì)，包括內(nèi)容管理、前臺(tái)展示、用戶權(quán)限管理、數(shù)據(jù)統(tǒng)計(jì)和安全保護(hù)等功能。

內(nèi)存限制：256.0MB C/C++時(shí)間限制：1.0s Java時(shí)間限制：3.0s Python時(shí)間限制：5.0s

問題描述

有一個(gè)箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時(shí)有n個(gè)物品（0＜n＜＝30），每個(gè)物品有一個(gè)體積（正整數(shù)）。
要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。

---

輸入格式

第一行為一個(gè)整數(shù)，表示箱子容量；
第二行為一個(gè)整數(shù)，表示有n個(gè)物品；
接下來n行，每行一個(gè)整數(shù)表示這n個(gè)物品的各自體積。

輸出格式

一個(gè)整數(shù)，表示箱子剩余空間。

---

樣例輸入

24 6 
8 3 12 7 9 7

樣例輸出

0

代碼–我自己的純代碼–純模擬–但可以過

#include#include 
using namespace std;
const int V = 2e4+5;
const int N = 30+5;
int a[N], v, n, book[V], flag[V];
int main()
{int m = 0;
	cin >>v >>n;
	for (int i = 1; i<= n; i++)cin >>a[i];
	sort(a + 1, a + 1 + n);//排序
	book[0] = 1;//初始化
	for (int i = 1; i<= n; i++)
	{if (a[i] >v)break;//如果單個(gè)數(shù)據(jù)就已經(jīng)大于V了就可以退出了
		for (int j = 0; j<= v; j++)
		{//第一	是存在的數(shù)
            //第二	新的數(shù)要在范圍內(nèi)
            //第三	不能是這次循環(huán)里才出現(xiàn)的數(shù)
            //第四	新出現(xiàn)的數(shù)不能是標(biāo)記過的數(shù)
			if (book[j] == 1 && j + a[i]<= v && flag[j] == 0 && book[j + a[i]] == 0)
			{		book[j + a[i]] = 1;//標(biāo)記已經(jīng)出現(xiàn)過
				flag[j + a[i]] = 1;//標(biāo)記這是新出現(xiàn)的數(shù)
				if (m< j + a[i])m = j + a[i];//取大值
			}
		}
		for (int j = 0; j<= v; j++)flag[j] = 0;//去除標(biāo)記
		if (m == v)break;//如果已經(jīng)達(dá)到V了也可以退出了
	}
	cout<< v - m;
	return 0;
}

大佬代碼–動(dòng)態(tài)規(guī)劃–1維背包

#includeusing namespace std;
inline int max(int a, int b) {return a >b ? a : b; }
int v, n;//v為箱子容量 , n個(gè)物品
int dp[20003];//箱子容量為i時(shí)，可裝入的大值
int a[33];
int main()
{cin >>v >>n;
	for (int i = 1; i<= n; i++)
		cin >>a[i];
	for (int i = 1; i<= n; i++)
		for (int j = v; j >= a[i]; j--)
			dp[j] = max(dp[j - a[i]] + a[i], dp[j]);
	cout<< v - dp[v];
	return 0;
}

再寫寫二維背包

#includeusing namespace std;
inline int max(int a, int b) {return a >b ? a : b; }
int v, n;//v為箱子容量 , n個(gè)物品
int dp[33][20003];
int a[33];
int main()
{cin >>v >>n;
	for (int i = 1; i<= n; i++)cin >>a[i];
	for (int i = 1; i<= n; i++)
		for (int j = 0; j<= v; j++)
		{//放的下，取大值
			if(j>=a[i])
				dp[i][j] = max(dp[i - 1][j - a[i]] + a[i], dp[i - 1][j]);
			else
				dp[i][j] = dp[i - 1][j];//放不下，直接就等于上一輪
		}
	cout<< v - dp[n][v];
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：試題算法訓(xùn)練裝箱問題-創(chuàng)新互聯(lián)
當(dāng)前URL：http://weahome.cn/article/gscjd.html