a455 - TOI2010 第四題：商品特賣問題
題目描述
題目描述一個商品特賣問題，給定 m 個箱子，每個箱子有不同的最大容量，以及 n 種商品的重量。目標是找出最多能裝入這些箱子的商品數量，每種商品最多只能選擇一次。
解題思路
本題的核心思想是貪心策略結合動態規劃。首先，對箱子的容量和商品的重量進行排序。然後，對於每個箱子，嘗試放入盡可能多的商品，使得總重量不超過箱子的容量。使用 dp 陣列來記錄在特定剩餘容量下，可以放入的最大商品數量以及對應的商品列表。對於每個箱子，從重量最大的商品開始嘗試放入，如果放入後剩餘容量仍然可以放入更多商品，則更新 dp 陣列。最後，累加每個箱子放入的商品數量，得到總的最大商品數量。used 陣列用於標記商品是否已被使用。
複雜度分析
- 時間複雜度: O(m * n^2)
- 空間複雜度: O(m * max_capacity) ，其中 max_capacity 是箱子容量的最大值。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,m,bx[55],a[1005],used[1005],ans;
vector <int> dp[3005];
int main(){
cin >> m >> n ;
for(int i=0;i<m;++i)
cin >> bx[i];
for(int i=0;i<n;++i)
cin >> a[i];
sort(bx,bx+m);
sort(a,a+n);
for(int i=0;i<m;++i){
for(int j=0;j<=bx[i];++j)
dp[j].clear();
int mx=0,mit=-1;
for(int j=n-1;j>=0;--j)
if(!used[j])
for(int k=a[j],l=0;k<=bx[i];++k,++l)
if(k==bx[i]||dp[l].size()<dp[k].size()+1){
dp[l]=dp[k];
dp[l].push_back(j);
if(dp[l].size()>mx){
mx=dp[l].size();
mit=k-a[j];
}
}
if(mx==0)break;
ans+=mx;
for(int j=0;j<dp[mit].size();++j)
used[dp[mit][j]]=1;
}
cout << ans;
}