注：n均为数量，t均为容积 ，w指各物品重量，c指各物品价值

背包问题，就是有n个物品，t格的背包，每个物品重量$w_i$，价值$c_i$,要求怎么装能利益最大化。自盘古以来就是一大世纪难题，不在于他有多难，而在于……

他们没有计算机！！！！！！

但是我们有计算机的还是听取WA声一片

一、刚学到排序的人

这么简单，这不是有手就行吗，直接一手排序找一下最贵的，把他选上，慢慢往后选不就行啦？

我直接一手提交。

#include<iostream>
#include<algorithm>
using namespace std;
int n,t,ans;
struct stu{
	int w;
	int c;
}a[1005];
bool lzh(stu x,stu y){
	if(x.c>y.c)return 0;
	else return 1;
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].c;
	}
	sort(a+1,a+n+1,lzh);//排序找最贵
	for(int i=1;i<=n;i++){
		if(t-a[i].w>=0){
			t-=a[i].w;
			ans+=a[i].c;
		}
	}
	cout<<ans;
	return 0;
} 

结果直接 WA 了……

随便出个样例都能卡他好吧

3 2
2 100
1 90
1 80

他代码输出的

100

但是明眼人都能看出来，你选后面俩不就有170块了吗？

二、很会贪心的！

我知道了！我们只需要把每个物品每格的价值算出来，选出每格价值最大的，再往下选不就行了

还是那句话，代码走起！

#include<iostream>
#include<algorithm>
using namespace std;
int n,t,ans;
struct stu{
	int w;
	int c;
}a[1005];
bool lzh(stu x,stu y){
	if(x.c/x.w>y.c/y.w)return 0;
	else return 1;
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].c;
	}
	sort(a+1,a+n+1,lzh);//排序找性价比最高 
	for(int i=1;i<=n;i++){
		if(t-a[i].w>=0){
			t-=a[i].w;
			ans+=a[i].c;
		}
	}
	cout<<ans;
	return 0;
} 

结果呢，有一个过50分的吗？

还是那句话，随便一个样例就能卡掉；

2 3
2 40
3 41

每格最贵的是第一个，20元/格，但是选完了就不能选其他的了

但是你都有3格的背包了，选一个更贵的不是更香吗？

三、万物皆可搜大手子

既然贪心都不行，那就只有一个办法了……

暴搜出奇迹！

#include<iostream>
#include<algorithm>
using namespace std;
int n,t,ans,w[200],c[200];
bool vis[200];
void dfs(int sum,int wet){
	ans=max(sum,ans);
	for(int i=1;i<=n;i++){
		if(!vis[i]&&wet+w[i]<=t){
			vis[i]=1;
			dfs(sum+c[i],wet+w[i]);
			vis[i]=0;
		}
	}
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	dfs(0,0); 
	cout<<ans;
	return 0;
} 

背包DP:不好，他在吸收题目的能量！

DFS:去你妈个DP，我命由我不由天！AC不AC，我自己说了才算！！！！！！！