http://acm.hdu.edu.cn/showproblem.php?pid=1963
完全背包。
题意:给出初始资金,还有年数,然后给出每个物品的购买价格与每年获得的利益,要求在给出的年份后所能得到的最大本利之和。
思路:因为每种物品可以多次购买,可以看做是完全背包的题目,但是要注意的是,由于本金可能会很大,所以我们要对背包的大小进行压缩,值得注意的是,题目已经说了本金与物品的购买价格都是1000的倍数,所以我们可以将他们都除以1000来进行压缩,然后就是一道完全背包模板题了。
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 333 Accepted Submission(s): 142
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 |
#include<iostream> #include<cstring> using
namespace std; double
Max( double
x, double
y) { if (x>y) return
x; else return
y; } int
main() { int
t,i,j,year,kind,capital; int
c[100],w[100],f[100000]; cin>>t; while (t--) { memset (c,0, sizeof (c)); memset (w,0, sizeof (w)); cin>>capital>>year; cin>>kind; for (i=1;i<=kind;i++) { cin>>c[i]>>w[i]; c[i]=c[i]/1000; //进行压缩。 } while (year--) { int
s=capital/1000; //每年本金都是上一年本金与利息之和 memset (f,0, sizeof (f)); //每年都要重新存利息 for (i=1;i<=kind;i++) //完全背包 for (j=c[i];j<=s;j++) { f[j]=Max(f[j],f[j-c[i]]+w[i]); } capital+=f[s]; //每年的最大本利和 } cout<<capital<<endl; } return
0; } |
原文:http://www.cnblogs.com/cancangood/p/3585377.html