TOJ - 129

jd3

我原本的想法是把 主件和對應的附件作成一組
dp[ i ][ j ] 表示第 i 個主件有購買的情況下 j 元買到的最大價值
然後把對應的附件在這上面做無限背包
用前兩組的答案取max來做rolling ， 變成dp[i%2][j]


可是好像不太對=口=


主件一定購買的情況下怎麼更新價值啊啊啊...

allenwhale

給你個小提示:開兩條陣列做就好~~
再一個小提示:其實做背包問題時連滾動都不用唷~

jd3

allenwhale 發表於 2014-8-25 14:57
給你個小提示:開兩條陣列做就好~~
再一個小提示:其實做背包問題時連滾動都不用唷~ ...

我的描述好像沒有到位

貼個code求救QAQ


(啊啊我發現我錯誤了先刪CODE)

allenwhale

jd3 發表於 2014-8-25 19:42
我的描述好像沒有到位

貼個code求救QAQ

你的想法方向沒錯
但是有點小漏洞，例如你先用主件做01背包，再用做出來的結果作無限背包，但是你怎麼保證在座無限ˋ杯刀時用的的資訊是有拿主件的?因為01背包不保證一定有拿，所以不能只用一個陣列做

jd3

allenwhale 發表於 2014-8-25 19:59
你的想法方向沒錯
但是有點小漏洞，例如你先用主件做01背包，再用做出來的結果作無限背包，但是你怎麼保 ...

嗯嗯 剛才發現了變數亂用的問題@@
改完的CODE只對了部分測資...Orz

[C++] 純文本查看 復制代碼

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;


int n,m;
int dp[2][2000000];	// dp[i][j] = 第 i(%2) 個 core 加入購買清單後 j 元的最大價值 
int cost[128],value[128],core[128];


int main()
{
	// Init
	memset(dp, 0, sizeof(dp));
	
	scanf("%d%d", &n, &m);
	
	/*
	cout << "money : " << n << endl;
	cout << "item_count : " << m << endl;
	*/
	
	// Input
	for(int i = 1 ; i <= m ; i++)
	{
		scanf("%d%d%d", &cost[i], &value[i], &core[i]);
		value[i] *= cost[i];
	}
	
	
	// Buttom-up
	//	init
	for(int i = 0 ; i < n ; i++)
		dp[0][i] = 0;
	int core_count = 0;
	for(int i = 1 ; i <= m ; i++)
	{
		if(core[i] == 0)	// is core
		{
			core_count++;
			int line = core_count%2;
			
			/*
			cout << "process : line " << line << endl;
			cout << "core = " << i << endl;
			*/
			
			
			for(int k = 0 ; k <= n ; k++)
				cout << dp[line][k] << ",";
			puts("");
			
			
			for(int k = n ; k >= cost[i] ; k--)
				dp[line][k] = dp[line][k-cost[i]] + value[i];
				
				
			for(int k = 0 ; k <= n ; k++)
				cout << dp[line][k] << ",";
			
			
			
			for(int k = 1 ; k <= m ; k++)
			{
				if(core[k] == i)
				{
				//	cout << "get part : " << k << endl;
					for(int j = cost[k]+cost[i] ; j <= n ; j++)
					{
				//		printf("update[%d][%d]\n",line,j);
						dp[line][j] = max ( dp[line][j], dp[line][j-cost[k]] + value[k] );
					}
				}
			}
			
			
		//	cout << "line " << 1-line << " = max ( line " << line << ", line" << 1-line << endl; 
			for(int j = 0 ; j <= n ; j++)
			{
				dp[1-line][j] = max ( dp[1-line][j], dp[line][j] );
			//	cout << dp[1-line][j] << ",";
			}
			
		//	cout << endl;
		
		
		
			puts("\nafter sack");
			for(int k = 0 ; k <= n ; k++)
				cout << dp[line][k] << ",";
			puts("\n-----------------------------------------------");
			
		}
	}
	
//	cout << "print line : " << 1-core_count%2 << endl;
	printf("%d",dp[1-core_count%2][n]);
	
	return 0;
}

allenwhale

而且你這樣做不覺得01背包不見了嗎

jd3

allenwhale 發表於 2014-8-25 20:41
而且你這樣做不覺得01背包不見了嗎

我是想說陣列第 i-2 行 (mod 2)就是沒用過，陣列 i-1 行 (mod 2)  就是有用過 @@

allenwhale

但是這樣"只拿主件不拿附件"這種可能有可能會消失喔

jd3

.