VAR box:array[1..30] of integer;
h:array[0..20000] of boolean;
k,v,n,i:integer;

begin
fillchar(h,sizeof(h),false);
readln(v);
readln(n);
for i:=1 to n do
readln(box[i]);
h[0]:=true;
for i:=1 to n do
for k:=v downto box[i] do
begin
h[k]:=h[k] or h[k-box[i]];
if h[n] then begin writeln(0); halt; end;
end;
for i:=v downto 0 do if h[i] then break;
writeln(v-i);
end.
为什么不对。。

#include <cstdio>
#include <cstring>

using namespace std;

inline int max(int a,int b) {
return a>b?a:b;
}

int main(void) {
int v=0,n=0;
scanf("%d %d",&v,&n);
int c[n];
for (int i=0;i<n;++i)
scanf("%d",c+i);
int f[v+1];
memset(f,0,(v+1)*sizeof(int));
for (int i=0;i<n;++i)
for (int j=v;j>=0;--j)
if (j>=c[i])
f[j]=max(f[j],f[j-c[i]]+c[i]);
int ans=9999999;
for (int i=0;i<=v;++i)
if (v-f[i]<ans)
ans=v-f[i];
printf("%d\n",ans);
return 0;
}
QwQ我好菜

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 20010;
const int M = 10;
LL dp[N];
int v,n,a,MAX;
vector<int>V;
void add(int x)
{
int k = V.size();
for(int i = 0; i < k; i++)
if(V[i] + x <= v &&!dp[V[i] + x]) //优先没弄好，RE，orz
{
dp[V[i] + x] = 1;
MAX = max(MAX,V[i] + x);
V.push_back(V[i] + x);
}
}
int main()
{
while(~scanf("%d%d",&v,&n))
{
memset(dp,0,sizeof(dp));
V.clear();
V.push_back(0);
dp[0] = 1;
MAX = 0;
for(int i = 0; i < n; i++)
{
scanf("%d",&a);
if(MAX != v)
add(a);
}
printf("%d\n",v - MAX);
}
}

#include<stdio.h>
#include<string.h>

int dp[50][20020],v,n,w[50];

int f(int t,int v)
{
if(t==n) return 0;
if(dp[t][v]>=0) return dp[t][v];
dp[t][v]=f(t+1,v);
if(v>=w[t])
{
int temp=f(t+1,v-w[t])+w[t];
if(temp>dp[t][v]) dp[t][v]=temp;
}
return dp[t][v];
}

int main()
{
scanf("%d%d",&v,&n);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
memset(dp,-1,sizeof(dp));
printf("%d",v-f(0,v));
return 0;
}
记忆化搜索 0-1背包，只是物品体积和价值相同

。。。。。数组开小了，我的AC率呀 %>_<%

刚学动态规划就自己做出来了，我真是屌到没朋友～(￣▽￣～)~
设d(i,j)表示把前i个物体装到容量为j的箱子中的最大体积
则状态转移方程为d(i,j)=max{d(i-1,j),d(i-1,j-v[i])+v[i] |j>=v[i]}

int main() {
memset(d,0,sizeof(d));
cin>>V>>n;
//for (int i=1;i<=n;++i) cin>>v[i];
for (int i=1;i<=n;++i) {
cin>>v;
for (int j=0;j<=V;++j) {
d[i][j]=d[i-1][j];
if (j>=v)
d[i][j]=max(d[i][j],d[i-1][j-v]+v);
//printf("d(%d,%d)=%d\n",i,j,d[i][j]);
}
}
cout<<V-d[n][V];
return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
int n,v[50],V,f[20001];
int main()
{
scanf("%d%d",&V,&n);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+v[i]);
printf("%d",V-f[V]);
}

program xiangzi;
var
a,b:array[1..20000] of longint;
i,j,k,l,m,n,v:longint;
begin
readln(v);
readln(n);
for i:=1 to n do
readln(a[i]);
for i:=1 to n do
for j:=v downto a[i] do
if b[j-a[i]]+a[i]>b[j]
then b[j]:=b[j-a[i]]+a[i];
writeln(v-b[v]);
end.

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 332 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 332 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 332 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 332 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 332 KiB, score = 10
Accepted, time = 15 ms, mem = 332 KiB, score = 50
代码
#include <iostream>
#define MIN(A,B) A<B?A:B

using namespace std;

int main(){
int capacity;
int itemNum;
int last[20001];
int itemCap[31];
cin >> capacity >> itemNum;
for(int i = 1; i <= itemNum; i++)
cin >> itemCap[i];
for(int i = 0; i <= capacity; i++)
last[i] = i;
for(int i = 1; i <= itemNum; i++){
for(int j = capacity; j >= 1; j--){
if(j >= itemCap[i]) last[j] = MIN(last[j], last[j-itemCap[i]]);
}
}
cout << last[capacity] << endl;
}

#include<stdio.h>//使得被装入的箱子体积最大
int dp[31][20001],v[31],w[31];
int max(int a,int b)
{
if(a>b)return a;
else return b;
}
int main()
{
int i,j,vol,n;
scanf("%d%d",&vol,&n);
for(i=0;i<n;i++)
{
scanf("%d",&v[i]);
w[i]=v[i];
}
for(i=n-1;i>=0;i--)
{
for(j=0;j<=vol;j++)
{
dp[i][j]=(i==n-1?0:dp[i+1][j]);
if(j>=v[i])dp[i][j]=max(dp[i][j],dp[i+1][j-v[i]]+w[i]);
}
}
printf("%d",vol-dp[0][vol]);
return 0;
}
0-1背包的改编，将原来求的重量最大值改成体积最大就行了

01背包
#include<iostream>
#include<cstdio>
using namespace std;
int V;
int N;
int a[200000];
int f[200000];
int max1(int x,int y)
{
if(x>y) return x;
else return y;
}
int main()
{
scanf("%d",&V);
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
}

for(int i=1;i<=N;i++)
for(int v=V;v>0;v--)
{
if(a[i]<=v)
{
f[v]=max1(f[v],f[v-a[i]]+a[i]);
}
else
f[v]=f[v];
}
cout<<V-f[V];
return 0;
}

这就是我突然想到的思路，既然AC了，说明是没问题的。

当我用楼下的办法做这题，发现它每次枚举都是true的值，就是之前有的状态，中间都浪费掉了时间，大约40W次循环（拿20个物品的情况）但是我这个程序的思路是把每次的状态放入一个队列V中，lenv记录长度，每次只要枚举队列里的状态，PD判断该状态是否已经在队列里面了。

这样的话考虑最坏情况，也只要枚举1+2+3+....+19+20次循环因此我开了个300的V数组。

不知道这也算不算是动规。总之看大家题解好像还没有这个思路，发上来可以大家看看。另外谁能告诉下，是不是一道动态规划的题，有时候是不是动态规划的方法有很多种的啊？？？我看这些动规好像都写的各种各样的？还是说只有某一种算？

###block code
program P1133;
var v:array[1..300] of longint; //队列存储状态
pd:array[0..200000] of boolean; //是否存在该状态的背包
n,i,w,m,j,max,lenv:longint;
begin
read(n); read(m); fillchar(v,sizeof(v),0); max:=0; fillchar(pd,sizeof(pd),false);
pd[0]:=true;
lenv:=1;
for i:=1 to m do //干嘛要读入？直接拿来算
begin
read(w); //物品体积
for j:=1 to lenv do
if (v[j]+w<=n) and (pd[v[j]+w]=false) then //如果不超过背包总大小，同时不存在该状态
begin
inc(lenv); v[lenv]:=v[j]+w; pd[v[j]+w]:=true; //加入队列，判断是不是当前最大值
if v[j]+w>max then
max:=v[j]+w;
end;
end;

write(n-max); //答案
end.

请问这是动态规划么？我在自学= =前几星期都搞不懂。现在稍微懂了，虽然AC了不过求大家看看是不是动态规划。
枚举了好多啊- -粗略算了下有40W次循环，不过DPS貌似有100W次循环- -

写完后对此题萌生了一个新的想法，不知道也算不算是动态规划，它能把时间复杂度降低到只要循环约1 2百次。希望大家看看，是楼上。

###block code
program P1133;
var v:array[0..20000] of boolean; //记录是否有这种情况
n,i,w,m,j,max:longint;
begin
read(n); read(m); fillchar(v,sizeof(v),false); max:=0;
v[0]:=true;
for i:=1 to m do //不存物品重量直接读入计算
begin
read(w);
for j:=n-w downto 0 do //枚举的好厉害，怕怕
if v[j]=true then
begin
v[j+w]:=true;
if j+w>max then //找最大的情况
max:=j+w;
end;
end;

write(n-max); //剩余的背包数目输出
end.

program _1133zhuangxiang;
var n0,v0,i,j:longint;
Volume:array[1..100]of longint;
f:array[0..20000]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

function DP(n0,v0:longint):longint;// f数组为容量为v时的最大价值
begin
fillchar(f,sizeof(f),0);
for i:=1 to n0 do
for j:=v0 downto 0 do// 重新计算容量为j时的最大装箱量（加上第i个物品）
if Volume[i]<=j then// 只有还有空间时才重新计算最大值
f[j]:=max(f[j],f[j-Volume[i]]+Volume[i]);// 容量为j时 选上第i个物品总空间更大还是不选更大
exit(f[v0]);
end;

begin
read(v0,n0);
for i:=1 to n0 do
read(Volume[i]);
writeln(v0-DP(n0,v0));
end.
program _1133zhuangxiang;
var n0,v0,i,j:longint;
Volume:array[1..100]of longint;
f:array[0..20000]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

function DP(n0,v0:longint):longint;// f数组为容量为v时的最大价值
begin
fillchar(f,sizeof(f),0);
for i:=1 to n0 do
for j:=v0 downto 0 do// 重新计算容量为j时的最大装箱量（加上第i个物品）
if Volume[i]<=j then// 只有还有空间时才重新计算最大值
f[j]:=max(f[j],f[j-Volume[i]]+Volume[i]);// 容量为j时 选上第i个物品总空间更大还是不选更大
exit(f[v0]);
end;

begin
read(v0,n0);
for i:=1 to n0 do
read(Volume[i]);
writeln(v0-DP(n0,v0));
end.
program _1133zhuangxiang;
var n0,v0,i,j:longint;
Volume:array[1..100]of longint;
f:array[0..20000]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

function DP(n0,v0:longint):longint;// f数组为容量为v时的最大价值
begin
fillchar(f,sizeof(f),0);
for i:=1 to n0 do
for j:=v0 downto 0 do// 重新计算容量为j时的最大装箱量（加上第i个物品）
if Volume[i]<=j then// 只有还有空间时才重新计算最大值
f[j]:=max(f[j],f[j-Volume[i]]+Volume[i]);// 容量为j时 选上第i个物品总空间更大还是不选更大
exit(f[v0]);
end;

begin
read(v0,n0);
for i:=1 to n0 do
read(Volume[i]);
writeln(v0-DP(n0,v0));
end.

评测结果
编译成功

测试数据 #0: Accepted, time = 281 ms, mem = 391952 KiB, score = 10
测试数据 #1: Accepted, time = 281 ms, mem = 391952 KiB, score = 10
测试数据 #2: Accepted, time = 281 ms, mem = 391956 KiB, score = 10
测试数据 #3: Accepted, time = 234 ms, mem = 391948 KiB, score = 10
测试数据 #4: Accepted, time = 265 ms, mem = 391948 KiB, score = 10
Accepted, time = 1342 ms, mem = 391956 KiB, score = 50
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define M 10000
using namespace std;

int dp[M][M],i,j,V,n,w[M];

int main() {
// freopen("pack.in","r",stdin);
// freopen("pack.out","w",stdout);
memset(dp,0,sizeof(dp));
memset(w,0,sizeof(w));
scanf("%d", &V);
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d",&w[i]);
for(i = 1; i <= n; i++) {
for(j = V; j > 0; j--) {
if(j >= w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + w[i]);
else dp[i][j] = dp[i-1][j];
}
}
printf("%d",V - dp[n][V]);
}

var
v,n,i,j,t:integer;
w:array[1..30] of integer;
f:array[0..20000] of boolean;
begin
readln(v);readln(n);
for i:=1 to n do
readln(w[i]);
f[0]:=true;
for i:=1 to n do
for j:=v downto w[i] do//不能使用for j:=w[i] to v do
if f[j-w[i]] then f[j]:=true;
t:=v;
while not f[t] do
dec(t);
writeln(v-t);
end.

program ex1;

var
s: array[0..20000] of 0..1;
sv, v, n, i, j: integer;
begin
readln(sv);
readln(n);
s[0] := 1;
for i := 1 to n do
begin
readln(v);
for j := sv - v downto 0 do
if s[j] = 1 then
s[j + v] := 1;
end;
for i := sv downto 0 do
if s[i] = 1 then
begin
writeln(sv - i);
exit;
end;
end.

#include<iostream>
using namespace std;
int N,v,n[1000],f[1000000],i,j;
main()
{
cin>>v>>N;
for(i=1;i<=N;i++)
cin>>n[i];
for(i=1;i<=N;i++)
for(j=v;j>=n[i];j--)
f[j]=max(f[j],f[j-n[i]]+n[i]);
cout<<v-f[v];
}

#include<cstdio>
#define IOFileName "P1133"
const int maxV=20002;
int V,v,n,ans;
bool box[maxV]={true};
int main(){
//freopen(IOFileName".in","r",stdin);
//freopen(IOFileName".out","w",stdout);
scanf("%d\n%d\n",&V,&n);
for(int i=0;i<n;i++){
scanf("%d\n",&v);
for(int j=V;j>=0;j--){
if(box[j]&&j+v<=V){
box[j+v]=true;
}
}
}
for(ans=V;!box[ans];ans--);
printf("%d\n",V-ans);
}
260KB+0MS

注意输入数据的筛选：
#include <stdio.h>

int knapsack01[20001];

int main(){
int v;//0 = = 20000
int n;//0 = = 30
int vi[31];
int tempvi;//fliter those vi which > v & if vi == v then print 0
bool flag;//to print 0
int i,j;//for loop

while( ~scanf("%d%d",&v,&n) ){
flag = 0;

//input
for(i=1; i<=n; i++){
scanf("%d",&tempvi);
if(tempvi < v)
vi[i] = tempvi;
else if(tempvi > v){
n--;
i--;
}else{//tempvi == v
flag = 1;
break;
}
}

//special judge when n == 0
if(n == 0){
printf("%d\n",v);
continue;
}

//special judge when v == 0
if(v == 0){
printf("0\n");
continue;
}

//special judge when haveing vi == v
if(flag){
printf("0\n");
continue;
}

//knapsack01 init
knapsack01[0] = 0;
for(i=1;i<=v;i++)
knapsack01[i] = -1000000;//20000 * 30 - 1000000 < 0

//knapsack01 start
for(i=1; i<=n; i++)
for(j=v; j>=vi[i]; j--)
knapsack01[j] = knapsack01[j] > knapsack01[j - vi[i]] + vi[i] ? knapsack01[j] : knapsack01[j - vi[i]] + vi[i];

//search for the biggest v which saves the positive number
for(i=v; i>=0; i--)
if(knapsack01[i] >= 0)
break;

printf("%d\n",v-i);
}

return 0;
}