点击打开链接
Problem Description 急！灾区的食物依然短缺！ 为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。 请问：你用有限的资金最多能采购多少公斤粮食呢？
Input 输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。 Output 对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。 Sample Input 1 8 2 2 100 4 4 100 2 Sample Output 400
题解： 多重背包，利用二进制思想枚举所有情况，
将第 i 种物品分成若干件物品，其中每件物品有一个系数，这件物品的 费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1，且 k 是满足 n[i]-2^k+1>0 的最大整数。例如， 如果 n[i]为 13，就将这种物品分成系数分别为 1,2,4,6 的四件物品。
这样就将第 i 种物品分成了 O(log n[i])种物品，将原问题转化为了复杂度为 O(V*Σ log n[i])的 01 背包问题，是很大的改进。
#include<bits/stdc++.h> using namespace std; const int maxn=105; int n,m,p,h,c; int dp[maxn*5]; int w[maxn*5],v[maxn*5]; int main(){ int t; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); int cnt=0; scanf("%d %d",&n,&m); for(int i=1;i<=m;++i){ scanf("%d %d %d",&p,&h,&c); for(int j=1;j<=c;j=j<<1){ v[++cnt]=p*j; w[cnt]=h*j; c-=j; } if(c>0){ v[++cnt]=p*c; w[cnt]=h*c; } } for(int i=1;i<=cnt;++i){ for(int j=n;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } printf("%d\n",dp[n]); } return 0; } 模板？ 保存一下。
int c[105],w[105],num[105]; int dp[105]; int v,V,V1; void ZeroOnePack(int c, int w) { for(int v = V; v >=c; v--) { dp[v] = max(dp[v],dp[v-c]+w); } } void CompletePack(int c, int w) { for(int v = c; v <= V; v++) { dp[v] = max(dp[v],dp[v-c]+w); } } void MultiplePack(int c, int w, int num) { if(c * num >= V) { CompletePack(c,w); } else { int k = 1; while(k < num) { ZeroOnePack(k*c, k*w); num -= k; k <<= 1; } ZeroOnePack(num*c, num*w); } } int main() { int t; scanf("%d",&t); int n; int i; while(t--) { scanf("%d%d",&V,&n); for(i = 1; i <=n; i++) { scanf("%d%d%d",&c[i], &w[i], &num[i]); } memset(dp,0,sizeof(dp)); for(i = 1; i <= n; i++) { MultiplePack(c[i],w[i],num[i]); } printf("%d\n",dp[V]); } return 0; } Problem Description 急！灾区的食物依然短缺！ 为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。 请问：你用有限的资金最多能采购多少公斤粮食呢？
