方法1:
完全类似于$01$背包问题,将物品体积同时看作物品价值求解:
$f[i]$表示容量为$i$的背包最多能装多少价值的物品
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
int t,n;
int f[N];
int main(){
cin>>t>>n;
for(int i=1;i<=n;i++){
int v; cin>>v;
for(int j=t;j>=v;j--){
f[j]=max(f[j],f[j-v]+v);
}
}
//ans:
cout<<t-f[t];
return 0;
}
方法2:
$f[i]$表示容量为$i$的背包能否被填满。
状态转移方程:$f[i]=f[i]~|~f[i-v]$
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
int t,n;
bool f[N];
int main(){
cin>>t>>n;
f[0]=1;
for(int i=1;i<=n;i++){
int v;cin>>v;
for(int j=t;j>=v;j--)
f[j]=f[j]|f[j-v];
}
for(int i=t;i;i--){
if(f[i]) {
cout<<t-i<<endl;
break;
}
}
return 0;
}
大佬为啥方法2我开个数组收就错了开个形参收就对了..
请问这个N为什么不是开30,而是开到两万以上
因为这题 dp 中 $f_i$ 表示容量 为 $i$ 的背包能否填满, $i$ 的最大值就是容量上限 $V=20000$,所以开这么大。