本文共 2547 字，大约阅读时间需要 8 分钟。
pku 1384 Piggy-Bank 完全背包入门题目。
这里只是求的恰好装满，且是最小罢了。在恰好装满时只要给f[0] = 0; 其他的一个未定义状态负无穷正无穷即可。
#include #include #include #include #include #include #include #include #include #include #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a , b) ((a) < (b) ? (a) : (b))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 10007#define N 504using namespace std;//freopen("din.txt","r",stdin);int f[M],w[N],c[N];int main(){ //freopen("din.txt","r",stdin); int n,m; int T,i,j; scanf("%d",&T); while (T--){ scanf("%d%d",&n,&m); int V = m - n; scanf("%d",&n); for (i = 0; i < n; ++i){ scanf("%d%d",&w[i],&c[i]); } for (i = 0; i < M; ++i) f[i] = inf; f[0] = 0; for (i = 0; i < n; ++i){ for (j = c[i]; j <= 10000; ++j){ f[j] = min(f[j],f[j - c[i]] + w[i]); } } if (f[V] != inf) printf("The minimum amount of money in the piggy-bank is %d.\n",f[V]); else printf("This is impossible.\n"); } return 0;}
pku 2063 Investment 多次完全背包
题意：
给定初始金钱数，给出d种债券的利润 c[i],w[i]每年买c[i]的债券可得w[i]的利润。给定你的使用年份m，问我利用初始给定的钱数最后得到的最大总钱数。
思路；
将利润看做物品的w值，将债券钱数看做物品的花费。往背包容量为初始钱数的背包里面放物品所得的最大值（最大利润）这样求即可。。
#include #include #include #include #include #include #include #include #include #include #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a , b) ((a) < (b) ? (a) : (b))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 100007#define N 17using namespace std;//freopen("din.txt","r",stdin);int f[M];int c[N],w[N];int main(){ //freopen("din.txt","r",stdin); int i,j,T,d; int n,m; scanf("%d",&T); while (T--){ scanf("%d%d",&n,&m); scanf("%d",&d); for (i = 1; i <= d; ++i){ scanf("%d%d",&c[i],&w[i]); c[i] /= 1000; } while (m--){ for (i = 0; i < M; ++i) f[i] = 0; int tmp = n/1000; for (i = 1; i <= d; ++i){ for (j = c[i]; j <= tmp; ++j){ f[j] = max(f[j],f[j - c[i]] + w[i]); } } n += f[tmp]; } printf("%d\n",n); } return 0;}
待更新。。。
转载地址：http://jvtba.baihongyu.com/
View Code