Complete knapsack problem 1

Milk Pails

link ：https://ac.nowcoder.com/acm/contest/7163/E
source ： Cattle from

The main idea of the topic ： Give the capacity X Units and Y A pail of milk , Pour in after each filling M Unit barrels , Make sure there is no overflow , ask M How many units of milk can a barrel hold at most

The sample input ：

17 25 77

Sample output ：

76

Sample explanation ：
In this example, FJ fills the pail of size 17 three times and the pail of size 25 once, accumulating a total of 76 units of milk.

Ideas ：
Completely backpack ,$dp[i]=1$ It means that you can install $i$ Unit milk , otherwise $dp[i]=0$, The initial state $dp[0]=1$

AC Code ：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N];
int main() {
    
	freopen("Milk Pails.in", "r", stdin);
	int x, y, m;
	while (scanf("%d%d%d", &x, &y, &m) == 3) {
    
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for (int i = x; i <= m; i++) {
    
			dp[i] |= dp[i-x];
		}
		for (int i = y; i <= m; i++) {
    
			dp[i] |= dp[i-y];
		}
		for (int i = m; i >= 0; i--) {
    
			if (dp[i]) {
    
				printf("%d\n", i);
				break;
			}
		}
	}
	return 0;
} 

Fruit Feast

link ：https://ac.nowcoder.com/acm/contest/7163/I
source ： Cattle from

The main idea of the topic ： Every lemon you eat will make you feel full A, Every time you eat an orange, you feel full B, You can choose to drink water once , Satiety is halved , Rounding down , The greatest feeling of satiety is T, Ask about the maximum satiety you can achieve

The sample input ：

8 5 6

The sample input ：

8

Sample explanation ：
Eat an orange , Satiety is 6, Drink lots of water , Satiety is 3, Eat a lemon , Satiety is 5

Ideas ：
Completely backpack ,$dp[i]$ Indicates the feeling of satiety that can be obtained ,$dp[i]=1$ It means you can feel full $i$, otherwise $dp[i]=0$, The initial state $dp[0]=1$, When transferring, pay attention to halving and transferring

AC Code ：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+7;
int dp[N];
int main() {
    
	//freopen("Fruit Feast.in", "r", stdin);
	int t, a, b;
	while (scanf("%d%d%d", &t, &a, &b) == 3) {
    
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for (int i = a; i <= t; i++) {
    
			dp[i] |= dp[i-a];
		}
		for (int i = b; i <= t; i++) {
    
			dp[i] |= dp[i-b];
		}
		for (int i = 0; i <= t; i++) {
    
			dp[i/2] |= dp[i];
		}
		for (int i = a; i <= t; i++) {
    
			dp[i] |= dp[i-a];
		}
		for (int i = b; i <= t; i++) {
    
			dp[i] |= dp[i-b];
		}
		for (int i = t; i >= 0; i--) {
    
			if (dp[i]) {
    
				printf("%d\n", i);
				break;
			}
		}
	}
	return 0;
}