[C++] 純文本查看 復制代碼
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int dp[2][2000000]; // dp[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, &value, &core);
value *= cost;
}
// Buttom-up
// init
for(int i = 0 ; i < n ; i++)
dp[0] = 0;
int core_count = 0;
for(int i = 1 ; i <= m ; i++)
{
if(core == 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 ; k--)
dp[line][k] = dp[line][k-cost] + value;
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 ; 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;
}