输入格式
第一行为一个整数,表示箱子容量; 第二行为一个整数,表示有n个物品; 接下来n行,每行一个整数表示这n个物品的各自体积。输出格式 一个整数,表示箱子剩余空间。样例输入
2468312797样例输出0算法分析:01背包,简单DP
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define MAXN 2001 8 int d[MAXN]; 9 int a[31]; 10 int main()11 {12 int V,n;13 scanf("%d%d",&V,&n);14 memset(d,0,sizeof(d));15 for(int i=0;i =a[i];j--)19 d[j]=max(d[j],d[j-a[i]]+a[i]);20 printf("%d\n",V-d[V]);21 return 0;22 }