可以吧
by lzh009 @ 2024-04-30 16:51:18
@[lucy2012](/user/1252442) 但是有更好的做法（状压dp）：
```cpp
#include <bits/stdc++.h>
using namespace std;
int V,n;
bitset<20001> st;
int main ()
{
st[0]=1;
cin>>V>>n;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
st|=(st<<x);
}
for (int i=V;i>=0;i--)
if (st[i]) cout<<V-i,exit (0);
return 0;
}
```
实测AC。
by hhhcj @ 2024-04-30 16:51:35
哦，i和j得从0开始遍历
@[lucy2012](/user/1252442)
by lzh009 @ 2024-04-30 16:52:16
@[lucy2012](/user/1252442) 我橙了
by hhhcj @ 2024-04-30 16:52:19
@[lzh009](/user/952814) i不用
by hhhcj @ 2024-04-30 16:53:17
@[lzh009](/user/952814) 只会增加时间
by hhhcj @ 2024-04-30 16:53:40
这样:
```c
#include <bits/stdc++.h>
using namespace std;
int V,n,a[34],dp[34][20004];
int main(){
cin>>V>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=0;j<=V;j++){
if(a[i]>j)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
}
}
cout<<V-dp[n][V]<<endl;
return 0;
}
``` @[lucy2012](/user/1252442)
by lzh009 @ 2024-04-30 16:54:14
@[hhhcj](/user/1021663)
但是我从1开始遍历WA了（寄）
by lzh009 @ 2024-04-30 16:54:56
@[lzh009](/user/952814) 啊~~~~~~~~~~~~~·
by hhhcj @ 2024-04-30 16:56:21
@[lzh009](/user/952814) 我说的是 $i$！！！！！
by hhhcj @ 2024-04-30 16:57:13