话说POJ这完全背包的题并不多,而且这个也不是很裸,因为股票的价格都是1000的倍数,所以价格都除以1000,整个背包的容量也除以1000, 这样复杂度就降下来了,然后每年的话,由于有收益,所以背包容量还会变化
基本原理参考背包问题九讲。其核心部分与0-1背包中里面那层循环是反过来的
F[0::V ] = 0
for i = 1 to N
for v = Ci to V
F[v] = max(F[v]; F[v-Ci]+Wi)
经过试验这个是无法用0-1背包中的下界优化的 但是之前是可以对物品优化,比如Ci > Cj 但是Wi < Wj 所以这类物品肯定不要。然后相同花费的价值小的也不会要,这样能降很多的复杂度
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 10005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int f[45300];
int main()
{
#ifdef LOCAL
freopen("d:/data.in","r",stdin);
freopen("d:/data.out","w",stdout);
#endif
int t, v, m, i, j, year, w[12], c[12];
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &v, &year);
scanf("%d", &m);
int tmp = v;
for(i = 1; i <= m; i++)
{
scanf("%d%d", &c[i], &w[i]);
c[i] /= 1000;
}
while(year--)
{
v = tmp / 1000;
for(i = 0; i <= v; i++)
f[i] = 0;
for(i = 1; i <= m; i++)
{
for(j = c[i]; j <= v; j++)
f[j] = max(f[j], f[j - c[i]] + w[i]);
}
tmp += f[v];
}
printf("%d\n", tmp);
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告