背包专题积累

学习感悟：感觉十道二十道题目根本不够，对背包理解也没有那么好，一些题目也只是大体记住了方法，稍微一变形可能就不会了。
今天刚刚其中考完试，也是考的一塌糊涂，绩点高能有什么用，题目放水，改卷也放水，一切都是假象，题目稍微一难，便什么都不会。跟真正的学霸比起来我什么都不是，我必须看清自己的实力，看清自己和985学校的差距，不能因为在弱校里的一点小成绩就洋洋自得。
考试确实给了我不少打击，这段时间一直专注算法学习，专业课疏忽了不少，还是自己能力不够，鱼和熊掌不可兼得，只能提高做事效率，否则就要作出取舍。

01背包第K优解

dp[j][k]表示背包容量为j时的第k优解
加入第i个物品时，当前状态通过枚举所有解的情况推出

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int N=1005;
const int mod=1e9+7;
#define ll long long
#define inf 0x3f3f3f3f
int v[N],c[N],dp[N][N];
int n,m,kk,q;

void solve(){
    memset(dp,0,sizeof(dp));
    cin>>n>>m>>kk;
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++)cin>>c[i];

	for(int i=1;i<=n;i++){
		for(int j=m;j>=c[i];j--){
			set<int,greater<int> > st;
			for(int k=1;k<=kk;k++){
				st.insert(dp[j][k]);
				st.insert(dp[j-c[i]][k]+v[i]);
			}
			int k=0;
			for(set<int,greater<int> >::iterator it=st.begin();it!=st.end();it++){
				dp[j][++k]=*it;
			}
		}
	}
	cout<<dp[m][kk]<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>q;
	while(q--){
        solve();
	}
}

hdoj3466Proud Merchants

Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?

Input
There are several test cases in the input.

Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.

The input terminates by end of file marker.

Output
For each test case, output one integer, indicating maximum value iSea could get.

Sample Input

2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3
关键点在于你的钱少于Q时村民拒绝交易
关键排序x.p-x.q>y.p-y.q;

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
const int N=5005;
const int mod=1e9+7;
#define inf 0x3f3f3f3f
#define ll long long
int dp[N];
struct node{
	int p,q,v;
	bool friend operator <(const node&x,const node&y){
		return x.p-x.q>y.p-y.q;
	}
}a[N];

int main()
{
	ios::sync_with_stdio(0);
	int q=1,m,n;
	//cin>>q;
	while(cin>>n>>m){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)cin>>a[i].p>>a[i].q>>a[i].v;
		sort(a+1,a+1+n);
		for(int i=1;i<=n;i++){
			for(int j=m;j>=max(a[i].p,a[i].q);j--){
				
				dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v);

			}
		}
		cout<<dp[m]<<endl;
		
	}
	return 0;
}

买纪念品

When the winter holiday comes, a lot of people will have a trip. Generally, there are a lot of souvenirs to sell, and sometimes the travelers will buy some ones with pleasure. Not only can they give the souvenirs to their friends and families as gifts, but also can the souvenirs leave them good recollections. All in all, the prices of souvenirs are not very dear, and the souvenirs are also very lovable and interesting. But the money the people have is under the control. They can’t buy a lot, but only a few. So after they admire all the souvenirs, they decide to buy some ones, and they have many combinations to select, but there are no two ones with the same kind in any combination. Now there is a blank written by the names and prices of the souvenirs, as a top coder all around the world, you should calculate how many selections you have, and any selection owns the most kinds of different souvenirs. For instance:

And you have only 7 RMB, this time you can select any combination with 3 kinds of souvenirs at most, so the selections of 3 kinds of souvenirs are ABC (6), ABD (7). But if you have 8 RMB, the selections with the most kinds of souvenirs are ABC (6), ABD (7), ACD (8), and if you have 10 RMB, there is only one selection with the most kinds of souvenirs to you: ABCD (10).

输出最多买的物品，同时输出选择种数
有限制通常加一维表示限制

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
int dp[5005][2];
int main()
{
	int q;
	cin>>q;
	while(q--){
		int n,m,x;
		memset(dp,0,sizeof(dp));
		cin>>n>>m;
		for(int i=0;i<=m;i++)dp[i][1]=1;
		for(int i=1;i<=n;i++){
			cin>>x;
			for(int j=m;j>=x;j--){
				if(dp[j][0]==dp[j-x][0]+1){
					dp[j][1]+=dp[j-x][1];
				}
				else if(dp[j][0]<dp[j-x][0]+1){
					dp[j][0]=dp[j-x][0]+1;
					dp[j][1]=dp[j-x][1];
				}
			}
		}
		if(dp[m][0])printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[m][1],dp[m][0]);
		else printf("Sorry, you can't buy anything.\n");
	}

	return 0;
}

硬币

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make
changes with these coins for a given amount of money.
For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent
coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins.
So there are four ways of making changes for 11 cents with the above coins. Note that we count that
there is one way of making change for zero cent.
Write a program to find the total number of different ways of making changes for any amount of
money in cents. Your program should be able to handle up to 7489 cents.
输入n，输出多少种组成方法

#include<bits/stdc++.h>
using namespace std;
long long dp[8000];
int main()
{
	int a[6]={0,1,5,10,25,50};
	int n;
    dp[0]=1;
	for(int i=1;i<=5;i++){
        for(int j=a[i];j<=8000;j++){
            dp[j]+=dp[j-a[i]];
        }
	}

	while(cin>>n){
        cout<<dp[n]<<endl;
	}

	return 0;
}

同上完全背包+大数处理

Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:

    1 @ US$3 + 1 @ US$2

    1 @ US$3 + 2 @ US$1

    1 @ US$2 + 3 @ US$1

    2 @ US$2 + 1 @ US$1

    5 @ US$1

Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of 1.. 1.. 1..K (1 <= K <= 100).
两个数组，一个存高位一个存低位

#include<iostream>
using namespace std;
#define ll long long
const ll inf=1e18;
int main()
{
    int n,k;
	while(cin>>n>>k){
        ll dp[1005]={0},a[1005]={0};
        dp[0]=1;
        for(int i=1;i<=k;i++){
            for(int j=i;j<=n;j++){
                a[j]=a[j]+a[j-i]+(dp[j]+dp[j-i])/inf;
                dp[j]=(dp[j]+dp[j-i])%inf;
            }
        }
        if(a[n])cout<<a[n];
        cout<<dp[n]<<endl;
	}

	return 0;
}

POJ 2184 Cow Exhibition(01背包升级版+负数下标处理）

“Fat and docile, big and dumb, they look so stupid, they aren’t much
fun…”

• Cows with Guns by Dana Lyons

The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si’s and, likewise, the total funness TF of the group is the sum of the Fi’s. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.
负数倒序遍历

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int N=100005;
const int mod=1e9+7;
#define ll long long
#define inf 0x3f3f3f3f
int s,f,dp[2*N];
int n,q=1;
void solve(){
    memset(dp,-0x3f,sizeof(dp));
    dp[100000]=0;
    for(int i=1;i<=n;i++){
        cin>>s>>f;
        if(s<0&&f<0)continue;
        if(s>=0){
            for(int j=2*N-5;j>=s;j--){
                if(dp[j]>-inf)dp[j]=max(dp[j],dp[j-s]+f);
            }
        }
        else{
            for(int j=1;j<=200000+s;j++){
                if(dp[j]>-inf)dp[j]=max(dp[j],dp[j-s]+f);
            }
        }
    }
    int res=0;
    for(int i=100000;i<=2*N-10;i++)if(dp[i]>=0)res=max(res,i+dp[i]-100000);
    cout<<res<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	//cin>>q;
	while(cin>>n){
        solve();
	}
}

分组背包

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int n,m,dp[505],a[505][505];
int main()
{
	while(cin>>n>>m,n&&m){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=m;j>=0;j--){
				for(int k=1;k<=j;k++){
					dp[j]=max(dp[j],dp[j-k]+a[i][k]);
				}
			}
		}
		cout<<dp[m]<<endl;
	}
	return 0;
}

分组背包2

After months of hard working, Iserlohn finally wins awesome amount of scholarship. As a great zealot of sneakers, he decides to spend all his money on them in a sneaker store.

There are several brands of sneakers that Iserlohn wants to collect, such as Air Jordan and Nike Pro. And each brand has released various products. For the reason that Iserlohn is definitely a sneaker-mania, he desires to buy at least one product for each brand.
Although the fixed price of each product has been labeled, Iserlohn sets values for each of them based on his own tendency. With handsome but limited money, he wants to maximize the total value of the shoes he is going to buy. Obviously, as a collector, he won’t buy the same product twice.
Now, Iserlohn needs you to help him find the best solution of his problem, which means to maximize the total value of the products he can buy.
每种牌子的鞋至少买一种，问获得的最大价值

#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
using namespace std;
int n,m,kk,dp[15][10005];

struct node{
	int p,v;
};
vector<node> a[20];

int main()
{
	while(cin>>n>>m>>kk){
		int x,y,z,flag=0;
		memset(dp,-1,sizeof(dp));
		memset(dp[0],0,sizeof(dp[0]));
		for(int i=1;i<=kk;i++)a[i].clear();
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			cin>>x>>y>>z;
			a[x].push_back({y,z});
		}
		for(int i=1;i<=kk;i++){
			if(!a[i].size()){flag=1;break;}
			for(int u=0;u<a[i].size();u++){
			    for(int j=m;j>=a[i][u].p;j--){
			    	if(dp[i][j-a[i][u].p]!=-1)dp[i][j]=max(dp[i][j],dp[i][j-a[i][u].p]+a[i][u].v);
				    if(dp[i-1][j-a[i][u].p]!=-1)dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][u].p]+a[i][u].v);
			    }
			}
		}
		if(dp[kk][n]!=-1&&!flag)cout<<dp[kk][m]<<endl;
		else cout<<"Impossible\n";
	}
	return 0;
}