我写的多重+优化 16ms
贴下代码
顺便问下LZ的做法 貌似跟我的不同


Program P1276;
 const
      maxc=100000;
      maxn=10;
 var
      f:array[-maxc..maxc]of boolean;
	  v:array[-maxc..maxc]of longint;
      sum,w:array[1..maxn]of longint;
      cash,n:longint;
 procedure init;
 var i:longint;
  begin
     fillchar(sum,sizeof(sum),0);
     fillchar(w,sizeof(w),0);
     read(cash);
	 read(n);
	 for i:=1 to n do read(sum[i],w[i]);
	 readln;
	 fillchar(f,sizeof(f),false);
	 fillchar(v,sizeof(v),0);
  end;

 procedure main;
 var i,j,k,cmax,tmp:longint;
  begin
   cmax:=0;
   f[0]:=true;
   for i:=1 to n do
   begin
    for j:=cmax downto 0 do
	 if f[j] then
	  for k:=1 to sum[i] do
       begin
	    tmp:=j+w[i]*k;
		if tmp>cash then break;
		if (v[tmp]<>0)and(v[tmp]<v[j]+1) then break;
		v[tmp]:=v[j]+1;
		f[tmp]:=true;
		if tmp>cmax then cmax:=tmp;
	  end;
   end;
   writeln(cmax);
   end;



begin
  assign(input,'P1276.in');
  assign(output,'P1276.out');
  reset(input);
  rewrite(output);
  while not eof do
   begin
    init;
    main;
   end;
  close(input);
  close(output);
end.

• Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (82) lijingwei 2011-08-17 15:05:51
  • Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (98) jayhaizeizai 2011-08-17 15:13:50
    • Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (567) lijingwei 2011-08-17 15:16:48