题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
//f[i][j]表示从i到n在背包容量为j的情况下的最佳情况
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 1e3+10;
int f[N][N];
int w[N],v[N];
int main(){
int n,m;
cin>>n>>m;
/*当我们按照正序遍历物品时,在计算f[i][j]时,我们是从前往后考虑每个物品的选择情况。
在计算f[i][j]之前,我们已经计算出了f[i-1][j-v[i-1]]和f[i-1][j]的值。但是在计算f[i][j]时,我们需要用到f[i+1][j-v[i]]的值。
因为正序遍历物品,当计算到第i个物品时,f[i+1][j-v[i]]还没有计算出来,因为我们在计算f[i][j]之前,还没有考虑第i+1个物品的选择情况。所以,如果按照正序遍历物品,那么在计算f[i][j]时,f[i+1][j-v[i]]的值还没有被更新,无法正确计算出最优解。
倒序遍历物品可以解决这个问题。当我们倒序遍历物品时,在计算f[i][j]时,我们已经计算出了f[i+1][j-v[i]]和f[i+1][j]的值,因为我们先考虑了第i+1个物品的选择情况。所以,倒序遍历物品可以保证在计算f[i][j]时,f[i+1][j-v[i]]的值已经被正确更新,从而得到正确的最优解。
因此,为了确保在计算f[i][j]时能够使用到正确的f[i+1][j-v[i]]的值,第二段for循环采用了倒序遍历的方式。*/
for(int i = 1;i<=n;i){
cin>>v[i]>>w[i];
}
for(int i = n;i>=1;i–){
for(int j = 0;j<=m;j){
f[i][j] = f[i+1][j];
if(j>=v[i]) f[i][j] = max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
int v1 = m;
for(int i = 1;i<=n;i++){
if(v1<0) break;
if(i == n && v1 >= v[i])
{
printf(“%d “,i);
break;
}
else if(v1-v[i]>=0&&f[i][v1] == f[i+1][v1-v[i]]+w[i]){
cout<<i<<” “;
v1 = v1 - v[i];
}
}
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla