jessica机场:求教背包问题dp方程式
来源:百度文库 编辑:中科新闻网 时间:2024/05/11 17:02:30
问题描述
在n件物品取出若干件放在空间为m的背包里,每件物品的重量为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
注意:在本题中,所有的重量值均为整数。
【输入格式】
输入由三行组成,第一行有两个整数,n(1≤n≤100000)、m(1≤m≤10000);
第二行有n个数字,表示n个物品的重量。
第三行有n个数字,表示n个物品的价值。
【输出格式】
输出为一个整数,为最优方案的最大价值。
【输入样例】
输入文件名:01bb.in
4 100
30 48 30 50
30 48 30 50
输出文件名:01bb.out
98
pascal
这两天想了想,方程式如下
f[i,j]表示前i个球构成质量为j时的最大价值
weight数组纪录各个物品的质量
valuable数组纪录各个物品的价值 那么转移方程式应该如下:
if f[i-1,j-weight[i]]<>0 then f[i,j]:=f[i-1,j-weight[i]]+valuable[i]
谢谢各位的提示,自己想出来了,不过由于开不了100000*10000的数组,所以仍无法解决极限情况,怎么压缩,节省空间,希望有人给出方法。
在n件物品取出若干件放在空间为m的背包里,每件物品的重量为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
注意:在本题中,所有的重量值均为整数。
【输入格式】
输入由三行组成,第一行有两个整数,n(1≤n≤100000)、m(1≤m≤10000);
第二行有n个数字,表示n个物品的重量。
第三行有n个数字,表示n个物品的价值。
【输出格式】
输出为一个整数,为最优方案的最大价值。
【输入样例】
输入文件名:01bb.in
4 100
30 48 30 50
30 48 30 50
输出文件名:01bb.out
98
pascal
这两天想了想,方程式如下
f[i,j]表示前i个球构成质量为j时的最大价值
weight数组纪录各个物品的质量
valuable数组纪录各个物品的价值 那么转移方程式应该如下:
if f[i-1,j-weight[i]]<>0 then f[i,j]:=f[i-1,j-weight[i]]+valuable[i]
谢谢各位的提示,自己想出来了,不过由于开不了100000*10000的数组,所以仍无法解决极限情况,怎么压缩,节省空间,希望有人给出方法。