3 100 90 200
190 200
题目要求两个队伍的体重之和尽可能相近，假设所有队员的总质量为sum，那么两个队伍的质量分别约为:sum/2。那么现在我们用01背包来解决这个问题。如果背包的大小是sum/2,那么在可供选择的队员中选择，使得选择的队员的总质量不超过sum/2，那么这样就可以使得所选择的队员的总质量达到最接近sum/2，间接的，剩下的所有队员分给另外一个队伍。这样两个队员之间的质量差就最小了。
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 int main() 7 { 8 int n; 9 while(~scanf("%d",&n)) 10 { 11 int sum,t; 12 sum=0; 13 int P[101]; 14 for(int i=1;i<=n;i++) 15 { 16 scanf("%d",&P[i]); 17 sum+=P[i]; 18 } 19 t=sum/2; 20 int dp[45010]={0};//记的初始化 21 int sum1=0; 22 int sum2; 23 for(int i=1;i<=n;i++) 24 { 25 for(int j=t;j>=P[i];j--) 26 { 27 //状态转移方程 28 dp[j]=max(dp[j],dp[j-P[i]]+P[i]); 29 } 30 } 31 for(int i=1;i<=t;i++) 32 { 33 //寻找dp[]中的最大值 34 if(dp[i]>sum1) 35 sum1=dp[i]; 36 } 37 sum2=sum-sum1; 38 printf("%d %d\n",sum1,sum2); 39 } 40 41 return 0; 42 }
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说：
“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
可能有多组测试数据，对于每组数据，
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
42 6 1 35 25 70 59 79 65 63 46 6 28 82 962 6 43 96 37 28 5 92 54 3 83 93 17 22 0 0
117 334
这是一个标准的01背包问题，直接套标准模板吧
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int maxm = 101; 7 const int maxt =1001; 8 9 int main() 10 { 11 int T,M; 12 while(~scanf("%d %d",&T,&M)&&T!=0&&M!=0) 13 { 14 int dp[maxt]={0},p[maxm],t[maxm]; 15 for(int i=1;i<=M;i++) 16 { 17 scanf("%d %d",&t[i],&p[i]); 18 } 19 for(int i=1;i<=M;i++) 20 { 21 for(int j=T;j>=t[i];j--) 22 { 23 dp[j]=max(dp[j],dp[j-t[i]]+p[i]); 24 } 25 } 26 int Max=0; 27 for(int i=0;i<=T;i++) 28 { 29 if(dp[i]>Max) 30 Max=dp[i]; 31 } 32 printf("%d\n",Max); 33 } 34 return 0; 35 }
搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧。
每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).
对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
5 1 18467 6334 26500 19169 15724 7 1 29358 26962 24464 5705 28145 23281 16827 0 0
492804 1399489
动态方程：dp[i][j]=min(dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]),dp[i][j-1])
理解：dp[i][j]代表从j件物品里选取i对 首先把物品重量排序，当选取对数为i（i从1开始遍历）对时，j从2到n遍历（从2开始是因为选取一对时，物品件数最小为2）
物品数为j时（也就是j的当前值），涉及到两个问题:
1.选还是不选这个物品，若不选这个物品，那么就是从j-1件物品里选k对，即dp[i][j-1]
2.若选这个物品则上一个物品不能选，所以选取对数i要减去1，j要减去2，然后加上选的这个物品的平方差，即dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1])
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string> 5 #include<string.h> 6 #include<set> 7 #include<math.h> 8 using namespace std; 9 int dp[1005][2005]; 10 int a[2005]; 11 int main() 12 { 13 int n,k,i,j; 14 while(cin>>n>>k) 15 { 16 for(j=0;j<2005;j++) 17 dp[0][j]=0; 18 19 for(i=1;i<1005;i++) 20 for(j=0;j<2005;j++) 21 dp[i][j]=0x3fffffff; 22 23 for(i=1;i<=n;i++) 24 cin>>a[i]; 25 26 sort(a+1,a+n+1); 27 28 for(i=1;i<=k;i++) 29 for(j=2;j<=n;j++) 30 dp[i][j]=min(dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]),dp[i][j-1]); //动态转移方程 31 32 cout<<dp[k][n]<<endl; 33 } 34 }
解题思路：
题目意思为求n个物品，拿k对使得消耗的体力最少，或者说是这k对物品，每一对中两件物品的质量差平方最小，所以要使得质量差的平方小，只能排序后取质量相邻两个物品作为一对；
现在设f[i][j]为前i件物品组成k对所消耗的体力最小；
这时分两种情况含有第i件物品和不含有第i件物品（即第i件物品是不是含在第j对里）
1.含有i件物品 则有 f[i][j]=f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]);
2.不含第i件物品则有 f[i][j]=f[i-1][j];
所以动态转移方程为:f[i][j]=minn(f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]), f[i][j]=f[i-1][j]);
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define size 2005 4 #define INIF 2147483646 5 6 7 int f[size][1005]; 8 int minn(int a,int b) 9 { 10 return a<=b?a:b; 11 } 12 int cmp(const void *a,const void *b) 13 { 14 return *(int *)a-*(int *)b;// 从小到大排序 15 } 16 int main() 17 { 18 int n,k,i,j; 19 int val[size]={0}; 20 f[0][0]=0; 21 while(scanf("%d%d",&n,&k)!=EOF) 22 { 23 24 val[0]=0; 25 for(i=1; i<=n; i++) 26 scanf("%d",&val[i]); 27 qsort(val+1,n,sizeof(val[0]),cmp); 28 for(i=0; i<=n; i++) 29 for(j=1; j<=k; j++) 30 f[i][j]=INIF; 31 32 for(i=2; i<=n; i++) 33 for(j=1; j*2<=i; j++) 34 f[i][j]=minn(f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]),f[i-1][j]); 35 printf("%d\n",f[n][k]); 36 } 37 return 0; 38 }
题解：经典的dp 问题，设dp[i][j]表示的是已经拿到第i件物品时拿了2*k件
转移方程要么在前i件的时候包括第i件这样第i+1件一定要取此时dp[i][k] = dp[i-2][k-1]+a[i-1]，要么就是不包括滴i件，那么在dp[i][k+1]一定等于dp[i-1][k],两种情况取最小
但是只要是dp一定要注意边界条件，先看转移方程中有哪些是自己一定要处理出来的初始数据，当k == 0 的时候所有dp都是0；当转移的时候如果是2*k>=i 则不再转移，因为不可能出现了，一定要想清楚什么时候可以继续转移
特别注意：对于任何一道题，都要提前想明白点的编号是从1开始还是从0开始，然后后面的所有程序都要按照这个规则去写，因为编号的问题出的错，程序长了是不好改的。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 #define INF 0x7f7f7f7f 6 #define N 2010 7 int v[N]; 8 int a[N]; 9 int dp[N][N]; 10 int main() 11 { 12 int n , k; 13 while(~scanf("%d%d",&n,&k)) 14 { 15 for(int i= 0 ;i < n ; i++) scanf("%d",&v[i]); 16 sort(v,v+n); 17 for(int i = 1 ; i < n ; i++) a[i-1] = (v[i]-v[i-1])*(v[i]-v[i-1]); 18 //memset(dp,0x7f,sizeof(dp)); 19 for(int i = 0 ; i < n ; i++) 20 for(int j = i/2+1 ; j< n ;j++) dp[i][j] = INF; 21 for(int j = 0 ; j < n ;j++) dp[j][0] = 0; 22 dp[1][1] = a[0]; 23 for(int i =2 ;i < n ; i++) 24 for(int j = 1 ; 2*j <= i+1 ;j++) 25 dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+a[i-1]); 26 printf("%d\n",dp[n-1][k]); 27 } 28 return 0; 29 }
原文：https://www.cnblogs.com/jiamian/p/10727045.html