CSP202209_2

• CSP202209_2
  • 题目
  • 思路
    • DFS
    • DP
  • Code

题目

何以包邮

思路

DFS

直接DFS，对每件物品根据选与不选进行搜索。当前总价值已经大于答案或者已经满足条件了就显然没有搜索必要，对答案更新后直接回溯即可；所有物品被搜完作为搜索的最终边界。

时间复杂度较大，只能70pts。

DP

挺明显的01背包，直接求出所有容量对应的价值后，找大于等于 m 且最小的背包价值即可。

Code

1. DFS(70pts)

   #include<bits/stdc++.h>
   const int INF = 0x3f3f3f3f;
   using namespace std;
   
   int n, m;
   int ans = INF;
   int val[10010];
   
   void DFS(int now, int sum)
   {
   	if(sum > ans) return;
   	if(sum >= m)
   	{
   		ans = min(ans, sum);
   		return;
   	}
   	if(now > n) return;
   	DFS(now + 1, sum + val[now]);
   	DFS(now + 1, sum);
   	return;
   }
   int main()
   {
   	cin >> n >> m;
   	for(int i = 1; i <= n; i++)
   	{
   		cin >> val[i];
   	}
   	DFS(1, 0);
   	cout << ans;
   	return 0;
   }
   

2. DP(100pts)

   #include<bits/stdc++.h>
   const int INF = 0x3f3f3f3f;
   using namespace std;
   
   int n, m, ans = INF;
   int val[101];
   int dp[300010];
   
   int main()
   {
   	cin >> n >> m;
   	for(int i = 1; i <= n; i++)
   	{
   		cin >> val[i];
   	}
   	for(int i = 1; i <= n; i++)
   	{
   		for(int j = 300001; j >= val[i]; j--)
   		{
   			dp[j] = max(dp[j], dp[j - val[i]] + val[i]);
   		}
   	}
   	for(int i = 1;i <= 300001;i++)
   	{
   		if(dp[i] >= m)
   		{
   			ans = min(ans, dp[i]);
   		}
   	}
   	cout << ans;
   	return 0;
   }