b131 - NOIP2006 2.开心的金明

🔗 前往 ZeroJudge 原題

題目描述

題目描述金明在預算內購買物品，目標是最大化物品價格乘以重要度的總和。給定預算 N 和 m 件物品，每件物品有價格 v 和重要度 p。

解題思路

本題可以視為一個背包問題的變形。傳統背包問題通常是最大化物品的總價值，而此題是最大化價格與重要度的乘積的總和。由於預算限制，我們需要選擇在預算內能獲得最大乘積總和的物品組合。

程式碼使用動態規劃的思想，a[i] 表示在容量為 i 的情況下，可以獲得的最大乘積總和。程式遍歷每件物品，並更新 a 陣列。對於每件物品，如果當前容量足夠，則考慮是否選擇該物品，並更新 a 陣列中的最大值。

核心邏輯在 for(int i=m-x;i>=0;--i) 迴圈中，x 是物品的價格，y 是物品的價格乘以重要度。迴圈從 m-x 開始，表示如果選擇該物品，則需要從 i 的位置開始考慮。a[i+x]=max(a[i+x],a[i]+y) 更新了在容量為 i+x 的情況下，可以獲得的最大乘積總和。

複雜度分析

• 時間複雜度: O(m * N)
• 空間複雜度: O(N)

程式碼

#include <iostream>
using namespace std;
int m,n,x,y;
int main(){
	cin >> m >> n;
	int a[m+1]={0},ans=0;
	while(n--){
		cin >> x >> y;
		y*=x;
		for(int i=m-x;i>=0;--i){
			if(a[i]||!i){
				a[i+x]=max(a[i+x],a[i]+y);
				ans=max(ans,a[i+x]);
			}
		}
	} 
	cout << ans;
}