急!灾区的食物依然短缺! 为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金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
思路:
与01背包有异曲同工的之处,我们只要修改一下,比如把第一个案例中的 2 100 4分成4个 2 100,这样是不是就变成了01背包呢?!
状态转移方程:W[j] = max(W[j], W[j - pr[i]] + wight[i]),W[j]表示买j钱的大米重量
1 #include2 #include 3 #include 4 #include 5 #define maxn 500+5 6 using namespace std; 7 int main() 8 { 9 int T;10 cin >> T;11 while (T--)12 {13 int wight[maxn], W[maxn],pr[maxn];14 int n, m, nl,p,h,c,cl=0;15 cin >> n >> m;16 for (int i = 0; i < m; i++)17 {18 cin >> p >> h >> c;19 cl += c;20 if (i == 0)21 {22 for (int j = 0; j < c; j++)23 pr[j] = p, wight[j] = h;24 nl = cl;25 }26 else27 {28 for (int k = nl; k < cl; k++)29 pr[k] = p, wight[k] = h;30 nl = cl;31 } //以上的一大段都在把大米分堆赋值32 }33 34 for (int i = 0; i <=cl; i++)35 {36 W[i] = 0;37 }38 for (int i = 0; i = pr[i]; j--)41 {42 W[j] = max(W[j], W[j - pr[i]] + wight[i]);43 }44 }45 cout << W[n] << endl;46 }47 return 0;48 }
提交的时候一直错误:
原因如下:
1、数组开小了,之前开的是500+5
2、用memset()给W[]赋值为0了,原来不能这样做,具体原因我也不晓得23333333
3、给W初始化的时候,循环要=cl。嗯!
一路坎坷,终于过了~~~~~~泪奔会儿。。。o(>_<)o ~~