反例易举
3 3 2 0
2 10 10
1 1 1
10 10 10
libojie 的程序输出 12，正确结果显而易见应为 4。
然而他的程序却通过了，这只能说明我的数据较弱 - -||
以这种形式并没有什么意思，只是因为 NOIP 复赛在即，希望大家不要被这种做法误导，这实际上是一种不完全的贪心算法，如果比赛时没有时间研究正解也不失为一种骗分技巧。
正解请参见本次比赛的题解，renqing 已发 PDF，数学算式部分我尽快联系 renqing 修复。鉴于本题的分析及运算较复杂，需要采用单调队列进行优化，便只采用 PDF 形式发布题解，请见谅。
另外本题 pascal 程序在 rqnoj 上无法通过，需要标程和数据的请跟帖贴上邮箱。
反例易举
3 3 2 0
2 10 10
1 1 1
10 10 10
我的程序输出 12，正确结果显而易见应为 4。
错误的原因在于，我的程序在计算最优值时，没有考虑少几个当前物品可能更优的情况。
实质上，这个问题是限制个数的背包问题。
有这样一种贪心算法，程序如下
for(j=0；j<n；j++)
{ int x[max]={0}；
for(i=v[j]；i<=max；i++)
if(x[i-v[j]]<k&&f[i-v[j]]+w[j]>f[i])
{ f[i]=f[i-v[j]]+w[j]；
x[i]=x[i-v[j]]+1；
}
}
仍是用一个数组记录当前选定个数。
但需要注意的是，本算法要求尽量多选择当前物品（只要不足k个就能选），但实际上不一定多选当前，必须对选择的个数进行枚举。这样，时间复杂度就变成了O(n*m*k) 其中n为物品数，m为最大体积，k为限制个数。显然无法通过。而本题解采用的算法属于动态规划--贪心算法，虽然有反例，但对多数情况是成立的。尤其对较大的随机数据，由于算法的计算较优解性，这种贪心算法的正确性有一定保证。
事实上，多重背包问题有O(VN)的算法，就像wish所说，要用到单调队列优化，编程复杂度高（我也不会），NOIP不会考察的。万一考到了类似问题，与其超时4个点，不如贪心错2个点。在RQNOJ的类似问题中，只有一道题得了70分，其他的三四道（包括此题）都AC了。因此，这种动态规划-贪心算法是一种正确率较高的算法。
类似Miller-rabbin算法，虽然是随机化的，不保证正确性，但在要求速度的NOIP实战中有很大用处。
总之，这种算法如果想在NOIP中应用，要小心一些，万一全是极端数据呢？？？
不过有一点要反驳，单调队列的编程复杂度是很低的，主要是分析的过程较复杂。
下面为标程，不过遗憾的是在 rqnoj 上无法通过：
program travel(input, output)；
const
maxm = 1000；
maxn = 1000；
maxk = 1000；
var
df1, df2, dfpos, mpos, m1, m2, ans, n, m, k, w, t, i, j: longint；
d: array [1..maxm, 1..maxn] of longint；
f, g: array [1..maxn, 1..maxm] of longint；
queueOut, queueIn: array [1..maxm] of longint；
queueCur, queue, S: array [1..maxm, 0..maxn] of longint；
function min(a, b: longint): longint； inline；
begin
if a < b then
min := a
else
min := b
end；
function max(a, b: longint): longint； inline；
begin
if a > b then
max := a
else
max := b
end；
procedure maintain(v, p: longint)； inline；
begin
if v < df1 then
begin
df2 := df1；
df1 := v；
dfpos := p
end
else if (v < df2) and (p <> dfpos) then
df2 := v
end；
begin
fillchar(f, sizeof(f), 0)；
fillchar(g, sizeof(g), 0)；
fillchar(queue, sizeof(queue), 0)；
fillchar(queueOut, sizeof(queueOut), 0)；
fillchar(queueIn, sizeof(queueIn), 0)；
fillchar(queueCur, sizeof(queueCur), 0)；
readln(n, m, k, w)；
for i := 1 to m do
begin
queue[i, 0] := - maxlongint；
S[i, 0] := 0；
for j := 1 to n do
begin
read(d[i, j])；
S[i, j] := S[i, j - 1] + d[i, j]
end
end；
df1 := - w；
df2 := - w；
for i := 1 to n do
begin
m1 := df1；
m2 := df2；
mpos := dfpos；
df1 := maxlongint；
df2 := maxlongint；
dfpos := 0；
for j := 1 to m do
begin
// g[i, j] Stay in one travel agency
if k > 1 then
begin
if i = 1 then
g[i, j] := d[j, 1]
else
begin
while queueCur[j, queueOut[j]] < max(1, i - k + 1) do
inc(queueOut[j])；
g[i, j] := queue[j, queueOut[j]] + S[j, i]
end；
maintain(g[i, j], j)
end；
// f[i, j] Switch from another travel agency
if i = 1 then
f[i, j] := d[j, 1]
else
if j = mpos then
f[i, j] := m2 + w + d[j, i]
else
f[i, j] := m1 + w + d[j, i]；
maintain(f[i, j], j)；
if k > 1 then
begin
t := f[i, j] - S[j, i]；
while (t <= queue[j, queueIn[j]]) and (queueIn[j] >= queueOut[j]) do
dec(queueIn[j])；
inc(queueIn[j])；
queue[j, queueIn[j]] := t；
queueCur[j, queueIn[j]] := i
end
end
end；
ans := maxlongint；
for i := 1 to m do
begin
ans := min(ans, f[n, i])；
if k > 1 then
ans := min(ans, g[n, i])
end；
writeln(ans)
end.