2012-09-16 09:27:30Morris
[ZJ][背包問題+Greedy] a455. TOI2010 第四題：商品特賣問題
內容 ：
在一個年終大拍賣活動中，一家迪化街的商店推出了一個特賣活動，老闆說只要你花錢買4個箱子，第一個箱子最多可裝30公斤的商品，第二個箱子最多可裝
40公斤的商品，第三個箱子最多可裝50公斤的商品，第四個箱子最多可裝25公斤的商品。可以挑選的商品有十種，重量分別是15, 16, 30,
18, 19, 20, 21, 25, 24,
及17公斤。每一種商品最多只能挑一次，且一種商品不可拆開分到不同箱子中。假設產品加總的重量小於等於箱子的限定重量就一定裝得下這些產品，由於每樣產
品的售價一樣，因此若挑選能裝入4個箱子的商品種類愈多，便表示價值愈高。請你寫一個程式來算出最多可以裝入這些箱子的商品數目，以便估算是否划算。
輸入說明
：
第一行為兩個整数M及N以空白區分，其中M表示箱子的個數，而N表示商品的種類數。
第二行開始的M行各為每一個箱子可容納的最大重量(公斤)。從第M+2行開始的N行，則分別表示N種商品個別的重量(公斤) 。
其中0<M≤50，0<N≤1000。
輸出說明
：
顯示最多能够裝入這些箱子的商品數目。若找不到能裝入這些箱子的商品，請輸出0。
範例輸入
：
範例一： 4 10 30 40 50 25 15 16 30 18 19 20 21 25 24 17 範例二： 3 9 20 10 10 3 8 3 7 9 3 5 8 5
範例輸出 ：
範例一： 7 範例二： 7
提示
：
時限仿照原題，更改為10秒。 (2012/7/6 修改)
出處
：
2010 TOI 研習營初選
(管理：longbiau)
隨便做的做法, 不保證正確性
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;
char p[1000][3000];
int main() {
int m, n, i, j, k;
int C[1005], W[1005];
while(scanf("%d %d", &m, &n) == 2) {
for(i = 0; i < m; i++)
scanf("%d", &C[i]);
for(i = 0; i < n; i++)
scanf("%d", &W[i]);
sort(C, C+m);
sort(W, W+n, greater<int>());
int used[1000] = {};
int ans = 0;
for(i = 0; i < m; i++) {
int dp[3000] = {};
int mx = 0, tmpN;
memset(p, 0, sizeof(p));
dp[0] = 0;
for(j = 0; j < n; j++) {
if(used[j] == 0) {
for(k = C[i]; k >= 0; k--) {
if(k-W[j] >= 0 && dp[k-W[j]]+1 > dp[k]) {
dp[k] = dp[k-W[j]]+1;
p[j][k] = 1;
}
}
}
}
mx = dp[C[i]];
if(mx == 0) break;
ans += mx;
for(j = n-1, k = C[i]; j >= 0; j--) {
if(p[j][k]) {
used[j] = 1;
k -= W[j];
}
}
}
printf("%d\n", ans);
}
return 0;
}
隨便做的做法, 不保證正確性
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;
char p[1000][3000];
int main() {
int m, n, i, j, k;
int C[1005], W[1005];
while(scanf("%d %d", &m, &n) == 2) {
for(i = 0; i < m; i++)
scanf("%d", &C[i]);
for(i = 0; i < n; i++)
scanf("%d", &W[i]);
sort(C, C+m);
sort(W, W+n, greater<int>());
int used[1000] = {};
int ans = 0;
for(i = 0; i < m; i++) {
int dp[3000] = {};
int mx = 0, tmpN;
memset(p, 0, sizeof(p));
dp[0] = 0;
for(j = 0; j < n; j++) {
if(used[j] == 0) {
for(k = C[i]; k >= 0; k--) {
if(k-W[j] >= 0 && dp[k-W[j]]+1 > dp[k]) {
dp[k] = dp[k-W[j]]+1;
p[j][k] = 1;
}
}
}
}
mx = dp[C[i]];
if(mx == 0) break;
ans += mx;
for(j = n-1, k = C[i]; j >= 0; j--) {
if(p[j][k]) {
used[j] = 1;
k -= W[j];
}
}
}
printf("%d\n", ans);
}
return 0;
}