https://vjudge.net/problem/UVA-242

題意：

輸入s（每個信封能粘貼的最多郵票數量）和若干郵票組合，選出最大連續郵資最大的一個組合（最大連續郵資也就是用s張以內的郵票來湊1,2,3,4...n,如果無法湊成n+1，那么最大值也就是n了）。如果有多個最大值，則優先考慮郵票數少的，其次考慮郵票面值最大的那個更小的。

?

思路：

完全背包問題。

完全背包是物品無限，在這里和題意相符合，每種郵票也是可以無限使用的。最大連續郵資就相當于一個背包容量，d[i]表示當最大連續郵資為i時所需要的最少的郵票數量，如果d[i]>s，說明 i 是無法湊成的，最大連續郵資也就是 i-1 了。

1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn = 25; 8 const int INF = 0x3f3f3f3f; 9 10 int s, n, m; 11 int a[maxn]; 12 int dp[1005]; 13 int ans[25]; 14 15 16 int main() 17 { 18 //freopen("D:\\txt.txt", "r", stdin); 19 while (cin >> s && s) 20 { 21 int best = 0; //最大連續郵資 22 int Max=INF; //最大郵票的值 23 int number = INF; //郵票數量 24 cin >> n; 25 for (int i = 0; i < n; i++) 26 { 27 cin >> a[0]; 28 for (int j = 1; j <= a[0]; j++) 29 cin >> a[j]; 30 memset(dp, INF, sizeof(dp)); 31 dp[0] = 0; 32 int now = 0; 33 for (int j = 1; j <= s*a[a[0]]+1; j++) 34 { 35 for (int k = 1; k <= a[0] && j >= a[k]; k++) 36 dp[j] = min(dp[j], dp[j - a[k]] + 1); 37 if (dp[j]>s) 38 { 39 now = j - 1; 40 break; 41 } 42 } 43 if (now > best) //此時的最大連續郵資大于了之前的 44 { 45 best = now; 46 number = a[0]; 47 Max = a[a[0]]; 48 memcpy(ans, a, sizeof(a)); 49 } 50 else if (now == best) //如果相等時 51 { 52 if (a[0] < number) //首先考慮郵票數量少的 53 { 54 number = a[0]; 55 Max = a[a[0]]; 56 memcpy(ans, a, sizeof(a)); 57 } 58 else if (a[a[0]] < Max) //如果郵票數量一樣多，則優先考慮郵票最大的那張更小的 59 { 60 Max = a[a[0]]; 61 memcpy(ans, a, sizeof(a)); 62 } 63 } 64 } 65 printf("max coverage =%4d :", best); 66 for (int i = 1; i <= number; i++)printf("%3d", ans[i]); 67 puts(""); 68 } 69 return 0; 70 }

?

轉載于:https://www.cnblogs.com/zyb993963526/p/6380042.html

總結

以上是生活随笔為你收集整理的UVa 242 邮票和信封（完全背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。