清橙OJ A1133. 裝箱問題 （0-1背包）

題目來源：http://www.tsinsen.com/A1133

最近北京大學因為聯考原因OJ登不上了，poj和百練都登不上，改在清華的清橙OJ上做題吧

那麼問題來了，清華會不會也要聯考閱卷呢？

A1133. 裝箱問題

時間限制：1.0s   記憶體限制：256.0MB  

試題來源

NOIP2001 普及組

問題描述

　　有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30），每個物品有一個體積（正整數）。

　　要求n個物品中，任取若幹個裝入箱内，使箱子的剩餘空間為最小。

輸入格式

　　第一行為一個整數，表示箱子容量；

　　第二行為一個整數，表示有n個物品；

　　接下來n行，每行一個整數表示這n個物品的各自體積。

輸出格式

　　一個整數，表示箱子剩餘空間。

　　樣例輸入

24

6

8

3

12

7

9

7

樣例輸出

-----------------------------------------------------

解題思路

0-1背包

dp[v][n] = max( dp[v][n-1], dp[v-a[i]][n-1]+a[i]),          v>=a[i]

           = dp[v][n-1],                                                       v<a[i]

簡化為一維數組 dp[v] = max(dp[v], dp[v-a[i]]+a[i])

注意用一維數組時要從v到a[i]倒着周遊，否則第i次的dp結果會覆寫第i-1次的dp結果

-----------------------------------------------------

代碼

 二維dp

#include<iostream>
#include<fstream>
using namespace std;

int dp[20002][35] = {};
int a[35] = {};

int main()
{
#ifndef ONLINE_JUDGE
	ifstream fin("0206_8785.txt");
	int v,n,i,j;
	fin >> v >> n;
	for (i=1; i<=n; i++)
	{
		fin >> a[i];
	}
	fin.close();
	for (i=1; i<=n; i++)
	{
		for (j=v; j>=a[i]; j--)
		{
			dp[j][i] = max(dp[j-a[i]][i-1]+a[i], dp[j][i-1]);
		}
		for (j=a[i]-1; j>=0; j--)
		{
			dp[j][i] = dp[j][i-1];
		}
	}
	cout << v-dp[v][n];
	return 0;
#endif
#ifdef ONLINE_JUDGE
	int v,n,i,j;
	cin >> v >> n;
	for (i=1; i<=n; i++)
	{
		cin >> a[i];
	}
	for (i=1; i<=n; i++)
	{
		for (j=v; j>=a[i]; j--)
		{
			dp[j][i] = max(dp[j-a[i]][i-1]+a[i], dp[j][i-1]);
		}
		for (j=a[i]-1; j>=0; j--)
		{
			dp[j][i] = dp[j][i-1];
		}
	}
	cout << v-dp[v][n];
	return 0;
#endif
}
           

一維dp

#include<iostream>
#include<fstream>
using namespace std;

int dp[20002] = {};
int a[31] = {};

int main()
{
#ifndef online_judge
	ifstream fin("0206_8785.txt");
	int v,n,i,j;
	fin >> v >> n;
	for (i=0; i<n; i++)
	{
		fin >> a[i];
	}
	fin.close();
	for (i=0; i<n; i++)
	{
		for (j=v; j>=a[i]; j--)						// 倒着周遊，防止第i次循環的結果覆寫第i-1次的結果
		{
			dp[j] = max(dp[j-a[i]]+a[i], dp[j]);
		}
	}
	cout << v-dp[v];
	return 0;
#endif
#ifdef online_judge
	int v,n,i,j;
	cin >> v >> n;
	for (i=0; i<n; i++)
	{
		cin >> a[i];
	}
	for (i=0; i<n; i++)
	{
		for (j=v; j>=a[i]; j--)
		{
			dp[j] = max(dp[j-a[i]]+a[i], dp[j]);
		}
	}
	cout << v-dp[v];
	return 0;
#endif
}