| 比赛 |
叫图论的DP题 |
评测结果 |
AAAAA |
| 题目名称 |
装箱问题 |
最终得分 |
100 |
| 用户昵称 |
kZime |
运行时间 |
0.007 s |
| 代码语言 |
C++ |
内存使用 |
5.04 MiB |
| 提交时间 |
2017-08-30 20:40:09 |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
int n,V;
int a[31];
unsigned long long f[31][20001];
void in(){
cin>>V>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
}
void solve(){
for(int i=1;i<=n;i++)
for(int j=V;j>=0;j--){
if(j>=a[i])
f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
else f[i][j]=f[i-1][j];
}
}
void out(){
cout<<V-f[n][V];
}
int main(){
freopen("npack.in","r",stdin);
freopen("npack.out","w",stdout);
in();
solve();
out();
return 0;
}