蓝桥杯 ALGO-21 装箱问题（动态规划，01背包）
问题描述 ：有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式 ：第一行为一个整数，表示箱子容量； 第二行为一个整数，表示有n个物品；
接下来n行，每行一个整数表示这n个物品的各自体积。 输出格式 一个整数，表示箱子剩余空间。
样例输入 2468312797
样例输出 0
#include <iostream>
using namespace std;int dp[31][20001];int main(){int v,n;cin>>v>>n;for(int i=1;i<=n;i++) {int t;cin>>t;for(int j=1;j<=v;j++) {if(j>=t)dp[i][j]=max(dp[i-1][j],dp[i-1][j-t]+t);elsedp[i][j]=dp[i-1][j];}}cout <<v-dp[n][v];return 0;}新闻热点
疑难解答
