Time Limit: 1 second
Memory Limit: 128 MB【问题描述】
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入格式】
第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可 ），其中v<=100，w<=1000，s<=10。【输出格式】
第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
Sample Input
5 100080 20 440 50 930 50 740 30 620 20 1
Sample Output
1040
【题解】
【法1】
这种有限制物品数量的背包问题，和完全背包的二维形式类似。只要在枚举的时候加上一个限制条件即k <= num[i]即可。
f[i][j]表示前i个物品，所用容量不超过j所能获得的最大价值。
f[i][j] = max{f[i-1][j],f[i-1][j-k*w[i]]+ k*c[i];
【代码1】
#include#include int m,n,f[509][6010],w[509],c[509],num[509]; //f数组实际上可以换成一个二维的滚动数组。。这样很方便的。 void input_data(){ scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) scanf("%d%d%d",&w[i],&c[i],&num[i]);} void get_ans(){ memset(f,0,sizeof(f)); for (int i = 1;i <= n;i++) { for (int j = m;j >=0;j--) //其实从大到小或者从小到大都没差。因为是二维的。 { f[i][j] = f[i-1][j]; int k = 1; while (k <= num[i] && k*w[i] <= j) //如果能够更新解。就更新 k要小于等于num[i] { if (f[i][j] < f[i-1][j-k*w[i]] + k * c[i]) f[i][j] = f[i-1][j-k*w[i]] + k * c[i]; k++; } } } }void output_ans(){ printf("%d",f[n][m]); }int main(){ //freopen("F:\\rush.txt","r",stdin); input_data(); get_ans(); output_ans(); return 0; }
【法二】
一维形式。
设f[j]表示容量不超过j时，所能获得的最大价值。
则f[j] = max{f[j],f[j-k*w[i]] + k * c[i].
其实这种更新方式和二维的无异。只是少了一维。且更新方式固定了。只能让容量那层循环从大到小循环。
如果还是不明白可以把法1的程序和法2的程序在i那层后面输出一下f[m-10..m]，会发现两个程序，i相同时，f[i][j]和f[j]是一样的。
【代码2】
#include#include int m,n,f[6010],w[509],c[509],num[509]; void input_data(){ scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) scanf("%d%d%d",&w[i],&c[i],&num[i]);} void get_ans(){ memset(f,0,sizeof(f)); for (int i = 1;i <= n;i++) for (int j = m;j >=w[i];j--) //换成了一维的形式。这时就一定要从后往前递减了。 for (int k = 1;k <= num[i];k++) //其实更新方式和二维是一样的。先从后面的更新是因为不会影响前面f[1..j-1] //而更新完f[j]之后，更新f[1..j-1]又恰好与f[j]无关了。所以f[j]的更新方式是正确的，且不会影响到后续的更新。 { if (j-k*w[i] < 0) break; if (f[j] < f[j-k*w[i]] + k*c[i]) f[j] = f[j-k*w[i]] + k*c[i]; } }void output_ans(){ printf("%d",f[m]); }int main(){ //freopen("F:\\rush.txt","r",stdin); input_data(); get_ans(); output_ans(); return 0; }