分组背包（动态规划）动态规划

Description
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
Input
第一行：三个整数，v(背包容量，v<=200),n（物品数量，n<=30)和t（最大组号，t<=10）;
第2..n+1行：每行三个整数wi,ci,p，表示每个物品的重量、价值、所属组号。
Output
仅一行，一个数，表示最大总价值。
Sample Input

Sample Output

f[j]表示花费费用j能取得的最大权值，状态转移方程为：

【分组背包（动态规划）】 f[j]=max{f[j-w[a[i,k]]]+v[a[i,k]],f[j]|j>w[a[i,k]]}
(1<=i<=t,m>=j>=0,1<=k<=a[i,0])
f[v]即为所求。
时间复杂度： O(t^2*v)

程序： var f:array[0..200]of longint; w,v:array[0..30]of longint; a:array[0..30,0..200]of longint; n,m,i,j,k,t,p:longint;
function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end;
begin readln(m,n,t); for i:=1 to n do begin readln(w[i],v[i],p); inc(a[p,0]); a[p,a[p,0]]:=i; end; for i:=1 to t do for j:=m downto 0 do for k:=1 to a[i,0] do if j>=w[a[i,k]] then f[j]:=max(f[j-w[a[i,k]]]+v[a[i,k]],f[j]); writeln(f[m]); end.

版权属于: Chris 原文地址:http://blog.sina.com.cn/s/blog_83ac6af80102vari.html 转载时必须以链接形式注明原始出处及本声明。