uva10465（完全背包，要求装满背包）

justPassBy 2021-09-02 原文

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=1406&mosmsg=Submission+received+with+ID+15392606

给我们两个物品的费用，和一个背包的容量

要求我们使得背包容量浪费最少的情况下，选尽可能多的物品

即要求装满背包的完全背包问题，只要注意初始化就可以了，将dp[0]置为0，其他的dp[i]置为-1，表示不合法

然后一个状态必须从一个合法的转移而来，然后在合法的状态转移中选取最大值

dp后，我们逆序枚举容量，找到一个合法的dp状态

那么该dp状态就是浪费容量最少的状态

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;                   
16 const int INF = 1<<30;
17 /*
18 
19 */
20 int a[2];
21 int dp[10000 + 10];
22 int main()
23 {
24     int n, i, j;
25     while (scanf("%d%d%d", &a[0], &a[1], &n) != EOF)
26     {
27         for (i = 1; i <= n; ++i)
28             dp[i] = -1;
29         dp[0] = 0;
30         for (i = 0; i < 2; ++i)
31         for (j = a[i]; j <= n; ++j)
32         {
33             if (dp[j - a[i]] != -1)//在合法的状态转移中选取最大值
34                 dp[j] = max(dp[j], dp[j - a[i]] + 1);
35         }
36         for (j = n; j >= 1; --j)
37             if (dp[j] != -1)//找个一个合法状态
38             break;
39         if (j == n)
40             printf("%d\n", dp[j]);
41         else
42             printf("%d %d\n", dp[j], n - j);
43     }
44     return 0;
45 }