Summary of the 13th week

   This week I mainly read the blog about backpacking . There are many types of knapsack problems ：01 knapsack , Completely backpack , Multiple backpack , Group backpacks, etc . This kind of question focuses on the analysis of the topic , Find the corresponding backpack type . The following is a summary of the problems we have seen this week, and the problems we have learned more .

1.P1049 [NOIP2001 Popularization group ] Packing problem

The question ： There is a box with the capacity of V, At the same time there is n Items , Each object has a volume . requirement n An object in , Take any number of them and put them in the box , To minimize the remaining space in the box .

Answer key ：
   In fact, the first time I saw this question, I thought of searching , But then I thought it over , Backpacks can also do , And it's easier to do than search , Just understand that you need to change .
   Find the minimum remaining space , That is to say, the maximum weight that can be loaded . If we take the weight of an object as its value , Then the topic can be changed into a basic 01 knapsack problem . A box has two states ： Installed and not installed . Note No i Each box weighs w[i], For any weight m The maximum value of is recorded as f (m) , So we can get the state transition equation f（m）= max ( f ( m - w[i] ) + w[i], f (m) ). ordinary 01 knapsack problem , Difficulty is not great .

2. P1455 Buy with

The question ： A collocation is a set , Find the maximum value of a given value set .

Answer key ：
   This problem has been done in the practice of combining and searching sets , At that time, it was not done yet 01 The concept of backpack , The code written is cumbersome , Now it seems that 01 Backpacks are easier to do , So I'll sort it out here .
   This is a parallel search +01 Knapsack problem ,01 The restriction of backpack is to buy A Have to buy B, So you can combine several items into a large item by using the union search set , And then use 01 Just make a backpack .

for(int i=1; i<=tot; i++)
		for(int j=w; j>=newp[i]; j--) // Scrolling array 
			f[j]=max(f[j],f[j-newp[i]]+newv[i]);

3. The Values You Can Make

The question ： Yes n A coin , Coins have corresponding values , Now we have to pick out some coins to make up k element , The output of the selected coins can form different values of money .

Answer key ：
This question is similar to backpack , However, another status is added , Is whether it can form s, So state dp[i][j][p] In order to take into account article i Number , The current sum of all numbers is j, Composition and for p Whether a subset of is possible .
So we can get the state transition relationship ：
If you don't use the second i Number ,dp[i][j][p]=dp[i-1][j][p]
If section i A number but not a subset ,dp[i][j][p]=dp[i-1][j-ci][p]
If section i Number and subset take him ,dp[i][j][p]=dp[i-1][j-ci][p-ci].

Code ：

#include<bits/stdC++.h>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
const int INF_INT  = 0x3f3f3f3f;
const ll INF_LL  = 1e18;
const int MAXN =1e5+5;
const int MAXM = 1015;
int n,k;
int c[505];
bool dp[505][505][505];
vector<int> ans;
int main()
{
      while(cin>>n>>k)
    {
    
        dp[0][0][0]=1;
        for(int i=1;i<=n;i++)
        {
      cin >> c[i]; }

        for(int z=1;z<=n;z++)
        {
      for(int i=0;i<=k;i++)
            {
    
                for(int j=0;j<=i&&j<=k;j++)
                {
     if(dp[z-1][i][j] ||(i>=c[z]&&dp[z-1][i-c[z]][j]) || (j>=c[z]&&dp[z-1][i-c[z]][j-z[c]]))
        dp[z][i][j] = 1;
                }
            }
        }
        for(int i=0;i<=k;i++)
        {
     if(dp[n][k][i])
            {
     ans.push_back(i); }
        }
        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++)
        {
    cout<<ans[i]<<" ";}
        cout<<endl;
    }
}

4. P1284 Triangle ranch

The question ： Yes n A board , The length of each piece l[i] Are integers. , Make a triangle with all the planks to maximize the pasture area .

Answer key ：
We can use f[k][i][j] Before use k Can a board be enclosed on both sides and grow into i,j The triangle of .

At first I wanted to use f[a][b][c It means that the length of three sides is a,b,c The triangle of . But keep reporting the wrong . Later I read the explanation , The maximum side length of the original triangle =4040/2=800,800800*800 Obviously too big , So it's not possible .

The first k Put a board on i In this side ：
Before use k-1 Make a circle of boards i-a[k] and j The triangle of , namely f[k-1][i-a[k]][j].
The first k Put a board on j In this side ：f[k-1][i][j-a[k]].
The first k A board is placed in the third side ：f[k-1][i][j].

So we get the state transition equation ：
f[k][i][j]=f[k-1][i-a[k]][j] || f[k-1][i][j-a[k]] || f[k-1][i][j];

Last , enumeration i and j, Judge whether it can form a triangle .

Code ：

#include<bits/stdc++.h>
const int N=50;
const int L=800+10;
using namespace std;
int n,a[N],sum;
double ans;
bool f[L][L];
bool check(int x,int y,int z) 
{
      if(x+y>z&&x+z>y&&y+z>x) return 1;
	return 0;
}
double work(double x,double y,double z)
{
      double p=(x+y+z)/2;
	return sqrt(p*(p-x)*(p-y)*(p-z));
}
int main()
{
      int i,j,k;
	cin>>n;
	for(i=1;i<=n;i++){
    cin>>a[i]; sum+=a[i];}
	f[0][0]=1;
	for(k=1;k<=n;k++)
	  for(i=sum/2;i>=0;i--)
	    for(j=sum/2;j>=0;j--)
	    {
     if(i-a[k]>=0&&f[i-a[k]][j]) f[i][j]=1;
	      if(j-a[k]>=0&&f[i][j-a[k]]) f[i][j]=1; 
		}
	ans=-1;
	for(i=sum/2;i>0;i--)
	  for(j=sum/2;j>0;j--)
	  {
     if(!f[i][j]) continue;
	  	if(!check(i,j,sum-i-j)) continue;
	  	ans=max(ans,work(i,j,sum-i-j));
	  }
	if(ans!=-1) cout<<(long long)(ans*100)<<endl;
	else cout<<ans<<endl;
	return 0;
}

5. POJ 1384( Completely deformed )

The question ：
Give the initial weight and full weight of the piggy bank , Give me some gold coins , Gold coins have value and weight , Ask for the minimum value when the piglet is full .

Answer key ：
This problem is the conversion of multiple knapsack ideas into 01 knapsack .
stay 01 In the backpack , Consider accommodating i When an object , There are two possibilities to choose and not to choose .
But in the multiple knapsack problem , We can choose many times .

So we can get the transfer equation ：
dp[i][j] = max( dp[i-1][j], dp[i][j-weight[i] ] + value[i] )

Code ：

for( int i = 0; i < nObject; i++)
{
    
        for( int j = weight[i]; j <= sumweight; j++)
        {
    
               dp[j] = max[dp[j], dp[j-weights[i]] + value[i];
        }
}

summary ：
   These two weeks because there are various exams , Spend less time on backpacking , I feel that more practice is needed , Although the class is over , But mine ACM Learning has just begun , I still need to work harder , Continue to refuel during the summer vacation ！