Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 468 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 468 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 464 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 464 KiB, score = 10
测试数据 #4: TimeLimitExceeded, time = 1014 ms, mem = 464 KiB, score = 0
TimeLimitExceeded, time = 1060 ms, mem = 468 KiB, score = 40
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int w[31],n,v,used[31]={0};

int main(){
int i,min=2147483647,s;
cin>>v>>n;
for(i=1;i<=n;i++){
cin>>w[i];
}
while(used[0]==0){
s=0;
for(i=1;i<=n;i++){
s=s+w[i]*used[i];
}
if(v-s<=min && v-s>=0)min=v-s;
i=n;
do{
used[i]++;
if(used[i]==2)used[i]=0;
i--;
}while(used[i+1]==0);
}
cout<<min<<endl;
return 0;
}

var
vv,n,i,j:integer;
v:array[1..30]of integer;
f:array[0..20000]of boolean;
begin
fillchar(f,sizeof(f),0);
f[0]:=true; read(vv,n);
for i:=1 to n do readln(v[i]);
for i:=1 to n do
for j:=vv downto v[i] do
f[j]:=f[j] or f[j-v[i]];
for i:=vv downto 0 do
if f[i] then
begin j:=i;break; end;
writeln(vv-j);
end.

你们好，问下你们
为什么
用最大子序列和做这个题目不对？
代码如下
program box;
uses math;
var v,n,i,j,ans:longint;
a,f:array[0..30] of longint;
begin
read(v,n);
if n=0 then
begin
writeln(v);
halt;
end;
for i:=1 to n do
read(a[i]);
for i:=1 to n do
begin
for j:=1 to n do
if (f[j]+a[i]>f[i]) and (f[j]+a[i]<=v) then
f[i]:=f[j]+a[i];
if f[i]>ans then
ans:=f[i];
end;
writeln('v-ans);
end.

我靠， 数组 害人哪
一定要开大一些，它这个数据范围不靠谱的~~

var
v,n,i,j,p,a:integer;
f:array[0..20000]of boolean;
begin
readln(v);
readln(n);
fillchar(f,sizeof(f),false);
f[0]:=true;
for i:=1 to n do begin
readln(a);
for j:=v-a downto 0 do if f[j] then f[j+a]:=true //注意：之前WA是因为循环顺序反了！！！
end;
p:=v;
while not f[p] do dec(p);
writeln(v-p);
end.

var
v,n,i,j:longint;
vv:array[1..30]of longint;
jiazhi:array[1..30]of longint;
f:array[0..20000]of longint;
procedure init;
begin
readln(v);
readln(n);
fillchar(vv,sizeof(vv),0);
fillchar(jiazhi,sizeof(jiazhi),0);
fillchar(f,sizeof(f),0);
for i:=1 to n do begin readln(vv[i]);jiazhi[i]:=vv[i];end;
end;

function max(aa,bb:longint):longint;
begin
if aa>bb then exit(aa) else exit(bb);
end;

procedure dp;
begin
for i:=1 to n do
for j:=v downto vv[i] do
f[j]:=max(f[j-vv[i]]+jiazhi[i],f[j]);
end;

begin
init;
dp;
writeln(v-f[v]);
end.

var
v,n,c,i,j:integer;
f:array[1..20000]of integer;
begin
readln(v);
readln(n);
for i:=1 to n do
begin

readln(c);
for j:=v downto c do
if f[j-c]+c>=f[j]then f[j]:=f[j-c]+c;
end;

c:=v-f[v];

writeln(c);
end.

Var v,n,i,j:longint;
a,f:array[0..50000] of longint;
Function max(a,b:longint):longint;
Begin
If a>b then exit(a) else exit(b);
End;
Begin
Readln(v);
Readln(n);
For i:=1 to n do readln(a[i]);
For i:=1 to n do
For j:=v downto 0 do
If j-a[i]>=0 then
f[j]:=max(f[j],f[j-a[i]]+a[i]);
Writeln(v-f[v]);
Readln;
End.

include <cstdio>
include <cstring>
include <algorithm>
using namespace std;
int dp[20002],n,c[32],tot;
int main(){
while(scanf("%d%d",&tot,&n)==2){
for(int i=1;i<=n;i++) scanf("%d",c+i);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=tot;j>=c[i];j--){
if(dp[j-c[i]]+c[i]<=tot)
dp[j]=max(dp[j],dp[j-c[i]]+c[i]);
}
printf("%d\n",tot-dp[tot]);
}
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[20002],n,c[32],tot;
int main(){
while(scanf("%d%d",&tot,&n)==2){
for(int i=1;i<=n;i++) scanf("%d",c+i);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=tot;j>=c[i];j--){
if(dp[j-c[i]]+c[i]<=tot)
dp[j]=max(dp[j],dp[j-c[i]]+c[i]);
}
printf("%d\n",tot-dp[tot]);
}
}

var

vl,n,i,j:longint;

f:array[-1..300,-20000..20000] of longint;

v:array[-1..300] of longint;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y)

end;

begin

readln(vl);

readln(n);

for i:=1 to n do

readln(v[i]);

for i:=1 to n do

for j:=1 to vl do

if f+v[i]

求分析：

var

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

f:array[0..100000]of integer;

n,i,j,m,v,max:integer;

begin

readln(v);

readln(n);

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

fillchar(f,sizeof(f),0);

max:=0;

for i:=1 to v do

for j:=v downto a[i] do

begin

if (f[j-a[i]]+a[i]>f[j])and(f[j-a[i]]+a[i]max then max:=f[j];

end;

max:=v-max;

writeln(max);

end.

为什么有一组数据没过？哪里的问题？

编译通过...

├ 测试数据 01：答案正确... (0ms, 600KB)

├ 测试数据 02：答案正确... (0ms, 600KB)

├ 测试数据 03：答案正确... (0ms, 600KB)

├ 测试数据 04：答案正确... (0ms, 600KB)

├ 测试数据 05：答案正确... (0ms, 600KB)

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

Accepted / 100 / 0ms / 600KB

无脑写了个排序，错了一个点，然后发现原来是背包问题……

01背包，vijos好多01背包啊，一天好像做了3个01了...

点击查看代码

是价值和容量值一样的背包

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

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

begin

readln(maxv);

readln(n);

f[0]:=true;

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

for i:=1 to n do begin

readln(v);

for j:=maxv-v downto 0 do if f[j] then f[j+v]:=true;

end;

for i:=maxv downto 0 do

if f[i] then begin

maxv:=maxv-i;

break;

end;

writeln(maxv);

end.

#include

using namespace std;

int f[31][20001];

int main()

{

int n,v,i,j,a[31];

cin>>v>>n;

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

for(i=1;if[j])

f[i][j]=f[j-a[i]];

else

f[i][j]=f[j];

cout

编译通过...

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

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

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

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

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

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

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