2023年8月1日发(作者：)

HDUoj2602简单01背包问题这道背包问题算是最经典的了吧，思路倒是清晰，就是太着急，弄得⼩问题不断。我采⽤的是⼆维数组的⽅法，牺牲了空间，还有⼀种⼀维数组的⽅法更加简单。主要问题是考虑不全⾯。#include#include#includeusing namespace std;int main(){ int T;//case cin >> T; int va[1001][2];//value , volume int dp[1001][1001]; while(T--) { int n,v; cin >> n >> v; for(int i=1; i <= n; i++) cin >> va[i][0];//value for(int i=1; i <= n; i++) cin >> va[i][1];//volume memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++) for(int j = 0; j <= v; j++) { //dp[i][j] = max(dp[i-1][j],dp[i-1][j-va[i][1]]+va[i][0]); if(j >= va[i][1])

dp[i][j]=max(dp[i-1][j],dp[i-1][j-va[i][1]]+va[i][0]);

else

dp[i][j]=dp[i-1][j]; } cout << dp[n][v] << endl; } return 0;}刚写了⼀维数组的解法，也传上来，主要就是注意v要倒叙遍历#include#include#includeusing namespace std;int main(){ int T;//case cin >> T; int va[1001][2];//value , volume int dp[1005]; while(T--) { int n,v; cin >> n >> v; for(int i=1; i <= n; i++) cin >> va[i][0];//value for(int i=1; i <= n; i++) cin >> va[i][1];//volume memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++) for(int j = v; j >= va[i][1]; j--) { dp[j] = max(dp[j],dp[j-va[i][1]]+va[i][0]); } cout << dp[v] << endl; } return 0;}

2023年8月1日发(作者：)

HDUoj2602简单01背包问题这道背包问题算是最经典的了吧，思路倒是清晰，就是太着急，弄得⼩问题不断。我采⽤的是⼆维数组的⽅法，牺牲了空间，还有⼀种⼀维数组的⽅法更加简单。主要问题是考虑不全⾯。#include#include#includeusing namespace std;int main(){ int T;//case cin >> T; int va[1001][2];//value , volume int dp[1001][1001]; while(T--) { int n,v; cin >> n >> v; for(int i=1; i <= n; i++) cin >> va[i][0];//value for(int i=1; i <= n; i++) cin >> va[i][1];//volume memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++) for(int j = 0; j <= v; j++) { //dp[i][j] = max(dp[i-1][j],dp[i-1][j-va[i][1]]+va[i][0]); if(j >= va[i][1])

dp[i][j]=max(dp[i-1][j],dp[i-1][j-va[i][1]]+va[i][0]);

else

dp[i][j]=dp[i-1][j]; } cout << dp[n][v] << endl; } return 0;}刚写了⼀维数组的解法，也传上来，主要就是注意v要倒叙遍历#include#include#includeusing namespace std;int main(){ int T;//case cin >> T; int va[1001][2];//value , volume int dp[1005]; while(T--) { int n,v; cin >> n >> v; for(int i=1; i <= n; i++) cin >> va[i][0];//value for(int i=1; i <= n; i++) cin >> va[i][1];//volume memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++) for(int j = v; j >= va[i][1]; j--) { dp[j] = max(dp[j],dp[j-va[i][1]]+va[i][0]); } cout << dp[v] << endl; } return 0;}