#include

main()

{

int n,v,i,j,x,max=0;

bool a[20001]={false};

a[0]=true;

scanf("%d",&v);

scanf("%d",&n);

for(i=0;i=0;j--){

if(a[j]){

if(j+xmax)max=j+x;

}

}

}

}

printf("%d",v-max);

}

大牛们，为什么样例过不了，却AC了！！！

program p1133;

var a:array[-1..20000,-1..20000]of longint;

t:array[-1..20000]of longint;

max,i,j,n,m:longint;

begin

read(m,n);

for i:=1 to n do

read(t[i]);

for i:=1 to m do

a[0,i]:=m;

for i:=1 to n do

for j:=1 to m do

if j-t[i]a-t[i] then

a:=a-t[i] else a:=a;

max:=10000000;

for i:=1 to m do

if (a[n,i]=0) then max:=a[n,i];

writeln(max);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

没注意一些细节问题，2次才AC

额。。这么基础的背包问题我居然因为疏忽提交了两次。。。

无奈了。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

靠,那么明显的0-1背包问题楼下的用滚动数组看看呢?看不懂c语言...

var v:integer;

a:array[1..30]of integer;

n,t:integer;

procedure init;

var i:integer;

begin

readln(v);

readln(n);

for i:=1 to n do readln(a[i]);

end;

procedure main;

var dp,dp1:array[0..20000]of integer;

i,j:integer;

begin

fillchar(dp1,sizeof(dp1),-1);

dp1[0]:=1;

t:=0;

for i:=1 to n do

begin

dp:=dp1;

for j:=0 to t do

if (dp[j]>-1) and (j+a[i]t then t:=j+a[i];

end;

end;

end;

begin

init;

main;

writeln(v-t);

end.

为什么最后一个超时？

#include

#include

using namespace std;

main ()

{int v,n,i,j,dp[102][102]={0},a[202];

cin>>v>>n;

for (i=1;i>a[i];

for (j=1;j=0&&(dp[j-a[i]]+a[i]>dp[j]))

dp[i][j]=dp[j-a[i]]+a[i];

}

}

cout

program backpack;

var

n,k,i,max:integer;

a:array [1..30] of integer;

procedure put(p,s:integer);

var j:integer;

begin

for j:=0 to 1 do

begin

s:=s+a[p]*j;

if s

var

t,m,x,i,j:longint;

v:array[0..100000] of longint;

begin

read(t,m);

fillchar(v,sizeof(v),0);

for i:=1 to m do begin

read(x);

for j:=t-x downto 0 do

if v[j]+x>v[j+x] then v[j+x]:=v[j]+x;

end;

writeln(t-v[t]);

end.

0/1 背包,v[i]=w[i]:

var

i,j:longint;

v,w:array[0..30] of integer;

n,vv:longint;

s:array[0..30,0..20000] of longint;

procedure inti;

var

i:integer;

begin

read(vv);

read(n);

for i:=1 to n do

begin

read(v[i]);

w[i]:=v[i];

end;

end;

function max(a,b:integer):integer;

begin

if a>b then max:=a else max:=b;

end;

begin

inti;

for i:=1 to n do

for j:=1 to vv do

begin

if j>=v[i] then s:=max(s,s+w[i]) else s:=s;

end;

writeln(vv-s[n,vv]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

看错范围害死人啊！同志们注意！

耻辱，看成每个可以无限取......

#include int max(int a,int b){if(a>b) return a;else return b;}int main(){int i,j,v,n;int f[30000]={0},g[100];scanf("%d%d",&v,&n);for(i=0;i

program v1133;

var f:array[0..20000]of boolean;

n,i,j,k,vm,vmax,x:longint;

begin

readln(vm);readln(n);

for i:=1 to vm do f[i]:=false;

f[0]:=true;vmax:=0;

for i:=1 to n do begin

readln(x);

for j:=vmax downto 0 do if f[j] and (j+xvm then vmax:=vm;

end;

for i:=vm downto 0 do if f[i] then break;

writeln(vm-i);

end.

细心+边界！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

基础ing

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include

#include

#include

using namespace std;

long g[301]={0},f[301][3001]={0};/*g[i][1]为价值,g[i][2]为耗费的时间*/

long T=0,M=0;

void in(void)

{ long i;

//freopen("in.txt","r",stdin);

//freopen("out.txt","w",stdout);

scanf("%ld",&T);

scanf("%ld",&M);

for(i=1;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program dpzxwt;

var v,j,k:0..20000;

n,i:0..30;

w:array[0..30] of longint;

f0,f1:array[0..20000] of 0..1;

begin

readln(v);readln(n);

for i:=1 to n do readln(w[i]);

f0[0]:=1;

for i:=1 to n do begin

f1:=f0;

for j:=v downto w[i] do

if f0[j-w[i]]=1 then f1[j]:=1;

f0:=f1;

end;

for j:=v downto 0 do

if f0[j]=1 then begin k:=j;break;end;

writeln(v-k);

end.

学会动态规划的第二题!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第一次

const maxV=20000;maxN=30;

var f:array[1..maxN]……

……浪费AC率了……

program s2;

var a:array[1..20,1..20000] of boolean;

w:array[1..20] of longint;

i,j,n,v,ans:longint;

begin

readln(v);

readln(n);

for i:=1 to n do

readln(w[i]);

if n=0 then begin

writeln(v);

halt;

end;

if v=0 then begin

writeln('0');

halt;

end;

fillchar(a,sizeof(a),false);

a[1,w[1]]:=true;

for i:=2 to n do

for j:=1 to v do

begin

a:=a;

if j>w[i]

then if a=true then a:=true;

end;

for i:=v downto 1 do

if a[n,i]=true then begin

ans:=i;

break;

end;

writeln(v-ans);

end.

谁帮我看看哪错了啊???

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program p1133;

var

k:array [0..30,0..20000] of integer;

n,i,j,m,l:integer;

a:array [1..30] of integer;

function min(a,b:integer):integer;

begin

if a>b then exit(b)

else exit(a)

end;

begin

readln(l);

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to l do

k[0,i]:=i;

for i:=1 to n do begin

for j:=1 to a[i]-1 do k:=k;

k:=0;

for j:=a[i]+1 to l do k:=min(k,k);

end;

writeln(k[n,l]);

end.

01背包，偶是拿动规做的，呵呵