|
//完全背包問題, //問題dp[i+1][j]從i+1種物品選出不超過j重量的最大價(jià)值物集合 //放的這最后一件,這一件可能是新種類或者舊種類,舊種類變成dp[i][j]子問題,新種類變成dp[i+1][j-w[i]]+v[i]) //子問題dp[i][j],dp[i+1][j-w[i]] int dp[1001][1001]; int v[1000]; int w[1000]; int max(int a, int b) { if (a > b) return a; else return b; } int main() { int n, W; cin >> n >> W; for (int i = 0; i < n; i++) cin >> v[i] >> w[i]; for(int k=0;k<n;k++) for (int j = 0; j <=W; j++) { if (w[k] > j)//重量超過容量,，不放進(jìn)去 { dp[k + 1][j] = dp[k][j]; } else { dp[k + 1][j] = max(dp[k][j],dp[k + 1][j - w[k]] + v[k]); } } cout << dp[n][W]; cin >> dp[n][W]; return 0; } |
|
|
