完全背包问题直接理解解法:
设状态dp[j]为:重量为j的背包的最大价值是什么
当对于每一个背包他的下一件物品可能是题目给的N件物品中的其中一件
所以直接进行枚举:
dp[j] = max(dp[j],dp[j-v[i])]+w[i]) ;
C++ 代码
//完全背包问题
int main2(){
int N,V ;
int v[1000] ;
int w[1000] ;
int dp[1000] ;
memset(dp,0,sizeof(dp)) ;
cin>>N>>V ;
for(int i=0;i<N;i++){
cin>>v[i]>>w[i] ;
}
for(int j=1;j<=V;j++){
for(int i=0;i<N;i++){
dp[j] = j>=v[i] ? max(dp[j],dp[j-v[i]]+w[i]) : dp[j] ;
}
}
cout<<dp[V] ;
return 0;
}