算法訓練 裝箱問題 藍橋杯

問題描述

　　有一個箱子容量為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;
}