疑问：请问内层循环为什么要从大到小啊？
一维数组要从大到小遍历我能理解，二维数组的第二个for循环为什么也要从大到小才行呢？
//1035-简单背包问题
#include<bits/stdc++.h>
using namespace std;
int main(){
int s,n;
while(cin>>s>>n){
int w[n+1];
int dp[n+1][s+1];
for(int i=1;i<=n;i++){
cin>>w[i];
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=s;j++){ //这里j必须从大到小才行，为什么？
if(dp[i-1][j]==1) dp[i][j]=1;
else if(j-w[i]>=0){
if(dp[i-1][j-w[i]]==1)
dp[i][j]=1;
}
}
}
if(dp[n][s]==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
可以结合高分篇和满分篇的背包问题来看，搞懂了怎么从二维数组压缩为滚动数组再压缩为一维数组你就知道怎么改了。