用动态规划做,不用深度优先搜索,伪代码或思路即可,背包问题（snap.pas）设有一个背包,可以放入的重量为s.现有n件物品,重量分别是W1,W2,...,Wn,均为正整数,从n件物品中挑选若干件,使得放入背

Question

用动态规划做,不用深度优先搜索,伪代码或思路即可,
背包问题（snap.pas）
设有一个背包,可以放入的重量为s.现有n件物品,重量分别是W1,W2,...,Wn,均为正整数,从n件物品中挑选若干件,使得放入背包的重量正好是s.找到一组解即可.
输入格式：第一行是物品的总件数和背包的载重量,第二行是各物品的重量.
输出格式：各所选物品的序号和重量.
【样例】
Snap.in 5 10
1 2 3 4 5
Snap.out
Numbet:1 weight:1
Numbet:4 weight:4
Numbet:5 weight:5
伪代码就可以了,

Answer 1

开一个bool数组f,f[i][j]表示是否可以用前i件物品【刚好】占用j的容量,初始化f[0..n][1..s]=false,f[0][0]=true.然后：for i=1 to n for j=w[i] to s f[i][j]=f[i-1][j] or f[i-1][j-w[i]];最后输出结果只...