有一点问题就是为啥每个i下,j(体积)都要从1开始枚举
不能直接成vmax吗,因为背包的总体积不变啊,不管装几个,背包大小不会变
C++ 代码
#include<iostream>
using namespace std;
const int N=1010;
int n,vmax;//物品数量和背包总体积
int v[N],w[N],dp[N][N];
int main(){
cin>>n>>vmax;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=vmax;j++){
dp[i][j] = dp[i-1][j];
if (j>=v[i])//容易忽略
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] +w[i]);
}
cout<<dp[n][vmax]<<endl;
}
你不从1开始写后面的
dp[i - 1][j - v[i]]
怎么计算刚刚又手动模拟了一遍,更加理解这个过程了
是逐个推出来的