杭州交通信息网新化到汨罗高铁:求教背包问题dp方程式
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/28 19:03:25
问题描述
在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的数组，所以仍无法解决极限情况，怎么压缩，节省空间，希望有人给出方法。