2012-09-16 07:38:02Morris
[ZJ][多重背包+Greedy] a350. 3. 緞帶的購買問題
內容 ：
小明的老師想要買緞帶來布置教室。她想要利用緞帶(緞帶的花色一樣)做成各種不同大小的花飾垂吊在教室後面，它們所需的緞帶長度分列如下：
| 花飾型號 | A | B | C | D | E | F | G | H | I |
| 緞帶長度 | 8 | 16 | 24 | 32 | 40 | 48 | 56 | 64 | 80 |
輸入說明
：
第一行有一個正整數N (10 £ N £ 500)，N代表目前市面上所賣的緞帶長度。
第二行有9個正整數Ci (1 £ i £ 9，0 £ Ci £ 1000)，以空白分開，依序代表各花飾型號所需的數量。第一個整數C1為花飾型號A所需的數量，第二個整數C2為花飾型號B所需的數量，以此類推。若不需製作某一型號的花飾，則Ci = 0。
輸出說明
：
請輸出1個正整數，代表所需購買的緞帶數。若市面上所賣的緞帶長度過短以致於無法製作出所需的花飾，請輸出”NO SOLUTION!!”。
範例輸入 ：
輸入範例一 100 10 3 0 0 0 0 0 0 2 輸入範例二 70 0 0 0 0 0 0 0 0 100
範例輸出 ：
輸出範例一 3 輸出範例二 NO SOLUTION!!
提示
：
出處
：
100三重考區資訊學科能力競賽
(管理：pcshic)
這題是不是爛解過的我不知道, 但是我用以下的做法過了,
首先你要先了解什麼是多重背包
多重背包就是每件物品Ai有限制個數Ci, 在一個背包容量V的情況下, 價值最多為多少,
我當初以為多重背包是多個背包去拼湊, 所以沒有想那麼多, 但後來發現不是,
那 Greedy 的法則是什麼 ?
你必須由大容量的物品開始放置, 找到可以湊出最大容量的一組解, 之後從物品中剔除,
其中那一組解盡可能是字典順序最大的
#include <stdio.h>
int main() {
int n, i, j, k;
int A[10] = {0,1,2,3,4,5,6,7,8,10};
while(scanf("%d", &n) == 1) {
int C[10];
for(i = 1; i <= 9; i++)
scanf("%d", &C[i]);
n /= 8;
int ans = 0, sol = 1;
while(1) {
for(i = 1; i <= 9; i++)
if(C[i]) break;
if(i == 10) break;
int dp[100] = {}, sour[100][2];
dp[0] = 1;
for(i = 9; i >= 1; i--) {
if(C[i] > 0) {
for(j = n; j >= 0; j--) {
if(dp[j] == 0) {
for(k = 1; k <= C[i]; k++) {
if(j-k*A[i] < 0) continue;
if(dp[j-k*A[i]]) {
dp[j] = 1;
sour[j][0] = i;
sour[j][1] = k;
break;
}
}
}
}
}
}
int tmpN = n;
while(tmpN >= 0 && dp[tmpN] == 0) tmpN--;
if(tmpN == 0) {sol = 0;break;}
while(tmpN) {
C[sour[tmpN][0]] -= sour[tmpN][1];
tmpN -= A[sour[tmpN][0]]*sour[tmpN][1];
}
ans++;
}
if(sol)
printf("%d\n", ans);
else
puts("NO SOLUTION!!");
}
return 0;
}
這題是不是爛解過的我不知道, 但是我用以下的做法過了,
首先你要先了解什麼是多重背包
多重背包就是每件物品Ai有限制個數Ci, 在一個背包容量V的情況下, 價值最多為多少,
我當初以為多重背包是多個背包去拼湊, 所以沒有想那麼多, 但後來發現不是,
那 Greedy 的法則是什麼 ?
你必須由大容量的物品開始放置, 找到可以湊出最大容量的一組解, 之後從物品中剔除,
其中那一組解盡可能是字典順序最大的
#include <stdio.h>
int main() {
int n, i, j, k;
int A[10] = {0,1,2,3,4,5,6,7,8,10};
while(scanf("%d", &n) == 1) {
int C[10];
for(i = 1; i <= 9; i++)
scanf("%d", &C[i]);
n /= 8;
int ans = 0, sol = 1;
while(1) {
for(i = 1; i <= 9; i++)
if(C[i]) break;
if(i == 10) break;
int dp[100] = {}, sour[100][2];
dp[0] = 1;
for(i = 9; i >= 1; i--) {
if(C[i] > 0) {
for(j = n; j >= 0; j--) {
if(dp[j] == 0) {
for(k = 1; k <= C[i]; k++) {
if(j-k*A[i] < 0) continue;
if(dp[j-k*A[i]]) {
dp[j] = 1;
sour[j][0] = i;
sour[j][1] = k;
break;
}
}
}
}
}
}
int tmpN = n;
while(tmpN >= 0 && dp[tmpN] == 0) tmpN--;
if(tmpN == 0) {sol = 0;break;}
while(tmpN) {
C[sour[tmpN][0]] -= sour[tmpN][1];
tmpN -= A[sour[tmpN][0]]*sour[tmpN][1];
}
ans++;
}
if(sol)
printf("%d\n", ans);
else
puts("NO SOLUTION!!");
}
return 0;
}