其中dp[v1]表示容量为v1的箱子能够获得的最大物品体积(价值)
用V-dp[V]即是最终答案
同时,用滚动数组可省去定义v[n]的空间
#include <stdio.h> int dp[20001]; int GetMax(int a ,int b) { return a > b ? a : b; } int main() { int V,n,i,t,v; scanf("%d%d",&V,&n); for(t=0;t<n;t++) { scanf("%d",&v); for(i=V;i>=v;i--)//从后往前递推 dp[i] = GetMax(dp[i],dp[i-v]+v); } printf("%d\n",V-dp[V]); return 0; }
原文：http://www.cnblogs.com/520xiuge/p/5149534.html