物品数量有限的背包问题

来源：百度知道 编辑：UC知道 时间：2024/05/04 07:36:50
有 n 件物品x1, x2, …, xn , 每件物品有价值、重量和数量，分别记为：
v1, v2, …, vn
w1, w2, …, wn
c1, c2, …, cn
其中所有的 wi 均为整数。 现有一个背包，其最大载重量为m，要求从这n件物品中任取若干件。问背包中装入哪些物品后，可以使得所装物品的价值和最大？

用PASCAL

用单位价值，单位价值和最大，价值和一般最大。

完全被曝问题的改版，LZ去搜索一下就有了。

在原本动态规划的基础上增加数量这一个状态，就可以了。

只要把读入改一下，
program baibao0_1;

{$mode objfpc}{$H+}

uses
Classes, SysUtils
{ add your units here };
var
v,a:array[1..1000]of integer;
f:array[0..1000]of integer;
vol,i,j,n:integer;
begin
readln(n,vol);
for i:=1 to n do
readln(a[i],v[i],);
for i:=1 to n do
for j:=vol downto v[i] do
if f[j]<=f[j-v[i]]+a[i] then f[j]:=f[j-v[i]]+a[i];
writeln(f[vol]);
end.