题意:这题就是一个纯粹的裸01背包
分析:WA了好几次。01背包实现的一些细节没搞懂
1.为什么dp[i][j]赋初值为0而不是value[i]。由于第i个石头可能不放!
2.在进行状态转移之前要dp[i][j]=dp[i-1][j],不然肯定会WA啊。想想就明确了
3.终于结果是dp[n][v],不是每次求mx,由于状态转移就是这么推的啊
代码:
#include#include #include using namespace std;long long dp[1001][1001],va[1001],mx;int t,n,v,vo[1001];int main(){ cin>>t; while(t--){ cin>>n>>v; mx=-1; for(int i=1;i<=n;i++) cin>>va[i]; for(int i=1;i<=n;i++) cin>>vo[i]; for(int i=1;i<=n;i++) for(int j=0;j<=v;j++) dp[i][j]=0; //错误1 for(int i=1;i<=n;i++){ for(int j=0;j<=v;j++){ dp[i][j]=dp[i-1][j]; //错误2 if(vo[i]<=j) dp[i][j]=dp[i][j]>dp[i-1][j-vo[i]]+va[i]?dp[i][j]:dp[i-1][j-vo[i]]+va[i]; } } mx=dp[n][v]; //错误3 cout< <