题目：http://acm.hdu.edu.cn/showproblem.php?pid=2191
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 const int MAX = 100 + 10; 8 int V; 9 int f[MAX],Price[MAX],Weight[MAX],Amount[MAX];10 void OneZeorPage(int cost, int weight)11 {12 for(int i = V; i >= cost; i--)13 f[i] = max(f[i], f[i - cost] + weight);14 }15 void CompletePage(int cost, int weight)16 {17 for(int i = cost; i <= V; i++)18 f[i] = max(f[i], f[i - cost] + weight);19 20 }21 void multiplePage(int cost,int weight,int amount)22 {23 if(amount * cost >= V)24 {25 CompletePage(cost,weight);26 return;27 }28 int k = 1;29 while(k < amount)30 {31 OneZeorPage(k * cost, k * weight);32 amount -= k;33 k <<= 1;34 }35 if(amount > 0)36 OneZeorPage(amount * cost, amount * weight);37 return;38 }39 int main()40 {41 int n,m,t;42 scanf("%d", &t);43 while(t--)44 {45 scanf("%d%d", &n,&m);46 for(int i = 1; i <= m; i++)47 scanf("%d%d%d", &Price[i],&Weight[i],&Amount[i]);48 memset(f,0,sizeof(f));49 V = n;50 for(int i = 1; i <= m; i++)51 multiplePage(Price[i],Weight[i],Amount[i]);52 printf("%d\n",f[n]);53 }54 return 0;55 }
那为什么会有完全背包和01 背包的不同使用加判断呢？原因也很简单啊，当数据很大，大于背包的容纳量时，我们就是在这个物品中取上几件就是了，取得量时不知道的，也就理解为无限的啦，这就是完全背包啦，反而小于容纳量的就是转化为01背包来处理就是了，可以大量的省时间。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 const int MAX = 100 + 10; 8 int V; 9 int f[MAX],Price[MAX],Weight[MAX],Amount[MAX];10 int main()11 {12 int n,m,t;13 scanf("%d", &t);14 while(t--)15 {16 scanf("%d%d", &n,&m);17 for(int i = 1; i <= m; i++)18 scanf("%d%d%d", &Price[i],&Weight[i],&Amount[i]);19 memset(f,0,sizeof(f));20 V = n;21 for(int i = 1; i <= m; i++)22 {23 for(int k = 1; k <= Amount[i]; k++)24 {25 for(int j = V; j >= Price[i]; j--)26 {27 f[j] = max(f[j], f[j - Price[i]] + Weight[i]);28 }29 }30 }31 printf("%d\n",f[n]);32 }33 return 0;34 }