【问题分析】
- 分析题目可得此问题为01背包问题
- 因此题数据较小
- 所以可用枚举每一样物品选或不选的方法来写
【设计程序】
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 10 + 5;
struct node
{
long long s, b;//s 为配料的酸度, d 为配料的苦度
} a[N];//此处可以用二维数组来代替
long long minn = 1e9;//题目要求求最小值,所以把minn设为最大值
int n;
void dfs(int step, long long ss, long long sb, bool q)
//step 代表判断要判断第几钟配料 ss 表示目前的酸度,
// sb 表示目前的苦度, q表示有没有选过配料
{
if (q)//如果选过
minn = min (minn , abs(ss - sb) );//把minn更新为最小值
if (step == n + 1)//如果都判断过了
return ;//返回上一层
dfs (step + 1, ss * a[step].s, sb + a[step].b, 1);//选的情况
dfs (step + 1, ss, sb, q);//不选的情况
}
int main()
{
scanf ("%d", &n);
for (int i = 1;i <= n; i++)
scanf ("%lld%lld", &a[i].s, &a[i].b);
dfs(1, 1, 0, 0);
printf ("%lld", minn);
return 0;
}
【调试代码】
- 测试样例,
- 自测数据(边界值或特殊值)(因本题中边界值已给出, 所以不用测边界值)
自测1:
输入:
2
2 2
2 2
输出:
0
去吃饭咯!!!!!
完结撒花!!
标签:P2036,ss,minn,int,题解,long,PERKET,step,include From: https://www.cnblogs.com/Assassins-Creed/p/18018416