Vijos P1133 装箱问题 01背包

描述

有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。

格式

输入格式

第一行，一个整数，表示箱子容量；
第二行，一个整数，表示有n个物品；
接下来n行，分别表示这n个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

样例输入

样例输出

限制

每个测试点1s

来源

noip2001普及组第四题

---------------------------------------------------------------------------------------------------------------------------------------

一道很经典的01背包，价值即体积，上代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 23333
 4 int V,n;
 5 int dp[maxn],a[66];
 6 int read();
 7 int max(int,int);
 8 int main(){
 9     V=read();n=read();
10     for(int i=1;i<=n;i++)a[i]=read();
11     for(int i=1;i<=n;i++)
12        for(int j=V;j>=a[i];j--)
13           dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
14     printf("%d",V-dp[V]);
15     return 0;
16 }
17 int read(){
18     int ans=0,f=1;char c=getchar();
19     while('0'>c||c>'9'){if(c=='-')f=-1;c=getchar();}
20     while('0'<=c&&c<='9')ans=ans*10+c-48,c=getchar();return ans*f;
21 }
22 int max(int x,int y){
23     return x>y?x:y;
24 }

01背包