算法训练 装箱问题 蓝桥杯

问题描述

　　有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。

　　要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

　　第一行为一个整数，表示箱子容量；

　　第二行为一个整数，表示有n个物品；

　　接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

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

　　样例输入

　　24

　　6

　　8

　　3

　　12

　　7

　　9

　　7

样例输出

从顶向下实现背包问题动态规划，边界问题还是比较麻烦的，好处是可以只算必要的

#include<stdio.h>
#define min(a,b) a<b?a:b
long long V,n;
long long tiji[31]={0};
long long v[31][20000]={0};
long long f(long long i,long long j){
if(v[i][j])return v[i][j];
if(j==0)return 0;//第一列表示j==v[i],剩余体积为0
if(j<tiji[i])return v[i][j]=f(i-1,j);
return v[i][j]=min(f(i-1,j),f(i-1,j-tiji[i]));
}
int main(){
long long i,j;
scanf("%lld%lld",&V,&n);
for(i=1;i<=n;i++)
    scanf("%lld",&tiji[i]);
for(i=1;i<=V;i++){//第零行表示什么不拿，剩余体积就是它的体积
    v[0][i]=i;
}
printf("%lld",f(n,V));
return 0;
}