题意：
买债券，总共n种债券，分别给出价格和收益，给出本金和年数，每年的本金都会改变，问最后本金加收益的和
要点：
很明显的完全背包问题，只要每次改变本金就可以，但这里有个问题就是数目过大，直接开数组会爆内存。题目中说本金和债券的价格都是1000的倍数，所以开数组时可以压缩，价格同时除1000就行，读题还是非常重要的。
#include<stdio.h>#include<string.h>#include<stdlib.h>#define max(a,b) a>b?a:bint dp[100000],value[15],interest[15];int main(){int T,i,j;scanf("%d", &T);while (T--){int start, year,n;scanf("%d%d", &start, &year);scanf("%d", &n);for (i = 0; i < n; i++){scanf("%d%d", &value[i], &interest[i]);value[i] /= 1000;//债券的价格同时也要除1000}int val = start;while (year--){memset(dp, 0, sizeof(dp));start =val/1000;//start是作为压缩后的dp下标for (i = 0; i < n; i++)for (j = value[i]; j <= start; j++)dp[j] = max(dp[j], dp[j - value[i]] + interest[i]);val += dp[start];//收益和本金每年都要相加}printf("%d\n", val);}return 0;}
