Question

求解背包问题

在n个物品中选择m个，每个物品有两个值a[i],b[i],满足在a[i]最小的情况下b[i]尽量大。求伪代码。

Answer 1

用递归来搜索
function Make(i{处理第i件物品},j{剩余空间j}：integer):integer;
{初始时i=n，j=m}
begin
if i:=0 then
Make:=0;
if j>=a[i] then{剩余空间可以放下i}
r1:=Make(i-1,j-a[i])+b[i];{放入价值}
r2:=Make(i-1,j){不放入价值}
Make:=max（r1,r2);
end;
我是你50分就直接要代码了。。。

追问

可以写DP吗?

追答

好吧，本来想偷懒的。。。
好像刚才的回答有点问题，你能不能把题目详细的打一遍。。。
你问的真的是背包问题吗？

Answer 2

这题不用DP啊！普通模拟排序即可。
因为题目首先要求a[i]最小，也就是说若a[i]<a[j]，不管b[i]和b[j]关系如何， 物品i必然优于j
所以将物品按a[i]排序，从小到大
然后所有值小于a[m]的必然要取，接着取出所有和a[m]值相等的元素，
将其按b从大到小排序，逐个取出即可
judge = a[m]
for i = 1->n
begin
if a[i]=judge
begin
c[top] = b[i]
inc(top);
end;
end;
算了你如果看懂了文字说明就好了