完全背包問題1

Milk Pails

鏈接：https://ac.nowcoder.com/acm/contest/7163/E
來源：牛客網

題目大意：給出能裝X單位和Y單位牛奶的桶，每次裝滿后倒入M單位的桶，確保不會溢位，問M單位的桶最多能裝多少單位的牛奶

樣例輸入：

17 25 77

樣例輸出：

76

樣例解釋：
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.

思路：
完全背包， d p [ i ] = 1 dp[i]=1 dp[i]=1表示能夠裝 i i i單位的牛奶，否則 d p [ i ] = 0 dp[i]=0 dp[i]=0，初始狀態 d p [ 0 ] = 1 dp[0]=1 dp[0]=1

AC代碼：

#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

鏈接：https://ac.nowcoder.com/acm/contest/7163/I
來源：牛客網

題目大意：每吃一個檸檬飽腹感加A，每吃一個橘子飽腹感加B，可以選擇喝一次水，飽腹感減半，向下取整，最大飽腹感為T，問能達到的最大飽腹感

樣例輸入：

8 5 6

樣例輸入：

8

樣例解釋：
吃一個橘子，飽腹感為6，喝水，飽腹感為3，吃一個檸檬，飽腹感為5

思路：
完全背包， d p [ i ] dp[i] dp[i]表示能夠獲得的飽腹感， d p [ i ] = 1 dp[i]=1 dp[i]=1表示能夠達到飽腹感 i i i，否則 d p [ i ] = 0 dp[i]=0 dp[i]=0，初始狀態 d p [ 0 ] = 1 dp[0]=1 dp[0]=1，轉移的時候注意減半也需要轉移

AC代碼：

#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;
}