【日常學習】【背包DP（完全背包）】洛谷1616 瘋狂的采藥題解

這是一道典型的完全背包題目

先上題目···于是又要迎來洛谷那令人不知道說什麼的霸氣摘要···

洛谷1616 瘋狂的采藥

本題位址： http://www.luogu.org/problem/show?pid=1616

題目背景

此題為NOIP2005普及組第三題的瘋狂版。 此題為紀念LiYuxiang而生。

題目描述

LiYuxiang是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：“孩子，這個山洞裡有一些不同種類的草藥，采每一種都需要一些時間，每一種也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。” 

如果你是LiYuxiang，你能完成這個任務嗎？

此題和原題的不同點：

1.每種采藥可以無限制地瘋狂采摘。

2.藥的種類眼花缭亂，采藥時間好長好長啊！師傅等得菊花都謝了！

輸入輸出格式

輸入格式：

輸入第一行有兩個整數T（1 <= T <= 100000）和M（1 <= M <= 10000），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞裡的草藥的數目。接下來的M行每行包括兩個在1到10000之間（包括1和10000）的整數，分别表示采摘某種草藥的時間和這種草藥的價值。

輸出格式：

輸出一行，這一行隻包含一個整數，表示在規定的時間内，可以采到的草藥的最大總價值。

輸入輸出樣例

輸入樣例#1：

70 3
71 100
69 1
1 2
      

輸出樣例#1：

140
      

說明

對于30%的資料，M <= 1000；

對于全部的資料，M <= 10000。

完全背包問題（物體可以選無限件）解決方案：

for (int i=1;i<=m;i++)
	{
		for (int j=v[i];j<=t;j++)
		{
			f[j]=max(f[j],f[j-v[i]]+c[i]);
		}
	}
           

再看01背包如何解決：

for (int i=1;i<=n;i++)
    {
        for (int j=v;j>=a[i];j--)
        {
            f[j]=max(f[j],f[j-a[i]]+a[i]); 
        }
    } 
           

我們驚奇地發現，兩者的差別僅僅在于枚舉體積循環，01背包是倒序，完全背包是正序。這是因為01背包要保證求解f[j]時，f[j-c[i]]是f[i-1][j-c[i]]而不是f[i][j-c[i]]。而完全背包恰恰相反，因為物品可選無數件，我們“選這件”需要考慮這件可能已經選了一些的情況，是以要保證求解f[j]時，f[j-c[i]]指的是f[i][j-c[i]]。

對于完全背包問題的常數優化，可以用“一種簡單有效的優化”，就是把價值低于某物品且體積高于某物品的物品删去。背包九講中提到可以用O（n²）或者O（V+N）的方案實作，但我并不明白具體如何實作，是将該物品對應的兩個數組元素指派為0或某個值，還是怎麼樣？

無論如何，先把代碼放上來吧

//洛谷1616 瘋狂的采藥 背包DP（完全背包）
//copyright by ametake
#include
   
    
#include
    
     
#include
     
      
using namespace std;

const int maxn=10000+10;
const int maxt=100000+10;
int t,m,v[maxn],c[maxn];// v=volumeÌå»ý c=cost=value¼ÛÖµ 
int f[maxt];

int main()
{
	scanf("%d%d",&t,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&v[i],&c[i]);
	}
	for (int i=1;i<=m;i++)
	{
		for (int j=v[i];j<=t;j++)
		{
			f[j]=max(f[j],f[j-v[i]]+c[i]);
		}
	}
	printf("%d\n",f[t]);
	return 0;
} 
     
    
   
           

——浮天水送無窮樹，帶雨雲埋一半山