【題解】洛谷P1049[NOIP2001普及]裝箱問題 01背包

題目連結

#include<cstdio>
#include<algorithm>
using namespace std;
int a[50],f[20010];
int main(){
	//freopen("in.txt","r",stdin);
	int n,i,j,v;
	scanf("%d%d",&v,&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
	for(j=v;j>=0;j--)
	if(j>=a[i])f[j]=max(f[j],f[j-a[i]]+a[i]);
	printf("%d",v-f[v]);
	return 0;
}
           

總結

無