实验4-1 01背包
【问题描述】给定一个容量为C的背包，现有n个物品，每个物品的体积分别为s1,s2...sn,价值分别为v1,v2...vn。每个物品只能放入一次。背包最多能装入价值为多少的物品。
【输入形式】输入的第1行包含2个整数C和n，分别表示背包容量和物品个数。接下来n行，每行包含2个整数si和vi，分别表示物品的体积和价值。
【输出形式】输出1行中含有一个数字，表示背包能装入的物品的最大价值。
【样例输入】
9 4
2 3
3 4
4 5
5 7
【样例输出】
12
//实验4-1 01背包
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int v[N];
int w[N];
int main()
{
int c , n ;
cin >> c >> n;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> v[i] >> w[i];
}
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= c ; j ++ )
{
dp[i][j] = dp[i-1][j];
if( j >= v[i])
{
dp[i][j] = max(dp[i-1][j] , dp[i-1][j - v[i]] + w[i]);
}
}
}
cout << dp[n][c];
return 0;
} 实验4-2 所有点对的最短路径问题
【问题描述】给定一个非负的加权有向图G，求其中任意两个节点之间的最短路径。
【输入形式】输入的第1行包含2个整数n和m，表示图G中包含n个节点和m条边。接下来m行，每行中有3个整数i,j,w，表示从节点i到节点j存在一条边(节点编号从1开始)，该边的权重为w。
【输出形式】
输出最短路径矩阵，共包含n行，每行包含n个数字(数字之间使用空格分割)，表示该节点到其他节点的最短距离。
特别地，节点到自身的距离定义为0；如果节点之间无法到达，使用1e9+7表示他们之间的距离。
【样例输入】
3 5
1 2 2
1 3 9
2 1 8
2 3 6
3 1 1
【样例输出】
0 2 8
7 0 6
1 3 0
【思考】如果出现负边，如何进行改进
floyed
//实验4-1 01背包
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 0x7f7f7f;
int dp[N][N];
int v[N];
int w[N];
int main()
{
int n , edgenum;
cin >> n >> edgenum;
int x , y , w ;
memset(dp,INF,sizeof dp);
for(int i = 1 ; i <= n ; i ++ )
{
dp[i][i] = 0;
}
for(int i = 1 ; i <= edgenum ; i ++ )
{
cin >> x >> y >> w;
dp[x][y] = w;
}
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1; j <= n ; j ++ )
{
for(int k = 1 ; k <= n ; k ++ )
{
dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
}
}
}
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ )
{
cout << dp[i][j]<<" ";
}
cout <<"\n";
}
return 0;
} 实验4-3 矩阵链相乘
【问题描述】给定n个矩阵M1,M2...Mn，他们的维数分别是r1*c1,r2*c2...rn*cn，要求使用【动态规划】的策略求解矩阵连乘的最优计算代价(总乘法次数最少)。题目保证矩阵相乘一定是有效的。
例如有三个矩阵M1，M2，M3，他们的维度分别是2*10,10*2，2*10。按照矩阵乘法的结合律，可以先把M1和M2相乘，然后把结果和M3相乘，总的乘法次数为2*10*2+2*2*10=80次；也可以先把M2和M3相乘，再用M1去相乘，这种方式下总的乘法次数为10*2*10+2*10*10=400次。因此最优计算代价为80。
【输入形式】输入的第1行中有1个数字n，表示矩阵的个数；接下来n行，每行2个整数ri和ci，分别表示矩阵Mi的行数和列数。
【输出形式】输出1行中有一个数字，表示n个矩阵相乘的最优计算代价。
【样例输入】
3
2 10
10 2
2 10
【样例输出】
80
【说明】
n>=2
1<=ri,ci<=20
//3
#include <iostream>
using namespace std;
const int N=101;
const int MAXN = 0x3f3f3f3f;
int n,cost;
int row[N], col[N], dp[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> row[i] >> col[i];
}
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
}
for (int x = 2; x <= n; x++) {
for (int i = 1; i <= n - x + 1; i++) {
int t = i + x - 1;
dp[i][t] = MAXN;
for (int k = i; k < t; k++) {
cost = dp[i][k] + dp[k + 1][t] + row[i] * col[k] * col[t];
if (cost < dp[i][t]) {
dp[i][t] = cost;
}
}
}
}
cout << dp[1][n]<<"\n";
}实验4-4 最少费用购物——动态规划
问题描述：
商店中每种商品都有标价。例如，一朵花的价格是2 元。一个花瓶的价格是5 元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销售。例如，3 朵花的价格不是6 元而是5 元。2 个花瓶加1 朵花的优惠价是10 元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。
编程任务：
对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。
数据输入：
由文件input.txt 提供欲购商品数据。文件的第1 行中有1 个整数B（0≤B≤5），表示所购商品种类数。接下来的B 行，每行有3 个数C，K 和P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。K 表示购买该种商品总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多可购买5*5＝25 件商品。
由文件offer.txt 提供优惠商品价数据。文件的第1 行中有1 个整数S（0≤S≤99），表示共有S 种优惠商品组合。接下来的S 行，每行的第一个数描述优惠商品组合中商品的种类数j。接着是j 个数字对（C，K），其中C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后一个数字P（1≤ P≤9999 ）表示此商品组合的优惠价。
结果输出:
程序运行结束时，将计算出的所购商品应付的最少费用输出到文件output.txt 中。
输入文件示例 输出文件示例
input.txt offer.txt output.txt
2 2 14
7 3 2 1 7 3 5
8 2 5 2 7 1 8 2 10
找出问题的规律，设cost（a,b,c,d,e）表示购买商品组合（a,b,c,d,e）需要的最少费用，A[k],B[k],C[k],D[k],E[k]表示第k种优惠方案的商品组合。offer(m)是第m种优惠方案的价格。如果cost(a,b,c,d,e)使用了第m种优惠方案，则找出最优子问题的递归表达式：cost(a,b,c,d,e)=cost(a-A[m],b-B[m],c-C[m],d-D[m],e-E[m])+offer(m)【★动态规划的步骤一★】
即该问题具有最有子结构性质，可以用动态规划算法来实现。
#include <iostream>
using namespace std;
int sale[10][6] = { 0 }; //分别表示每个优惠中每个商品数量
int saleprice[10] = { 0 }; //优惠的价格
int good[6][4] = { 0 }; //id price 数量
int dp[6][6][6][6][6]; //存储结果
int n;//商品数目
int m;//优惠方案数量
void input() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> good[i][1] >> good[i][3] >> good[i][2];//编号 商品数量 单价
}
int salething[10] = { 0 }; //优惠总共有几个商品
int saleid[10][10] = { 0 }; //优惠商品的ID
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> salething[i];//本次优惠有几个商品
for (int j = 1; j <= salething[i]; j++) {
cin >> saleid[i][j];//商品id
cin >> sale[i][saleid[i][j]];//商品的数目
}
cin >> saleprice[i]; //这种方案优惠价格
}
}
int main() {
input();//输入自己的要求
dp[0][0][0][0][0] = 0;
for (int i = 0; i <= good[1][3]; i++)//第几种 数量
for (int j = 0; j <= good[2][3]; j++)
for (int k = 0; k <= good[3][3]; k++)
for (int l = 0; l <= good[4][3]; l++)
for (int p = 0; p <= good[5][3]; p++) {//单价
int minx = i * good[1][2] + j * good[2][2] + k * good[3][2] + l * good[4][2] + p * good[5][2];//2存的是单价 不存在初始化默认为0 所以计算结果就为零
for (int q = 1; q <= m; q++) {//m优惠方案数目 2
if (i - sale[q][good[1][1]] < 0 || j - sale[q][good[2][1]] < 0 || k - sale[3][good[3][1]] < 0 || l - sale[q][good[4][1]] < 0 || p - sale[q][good[5][1]] < 0)
continue;//跳过本次方案 商品不够
int t = dp[i - sale[q][good[1][1]]][j - sale[q][good[2][1]]][k - sale[q][good[3][1]]][l - sale[q][good[4][1]]][p - sale[q][good[5][1]]] + saleprice[q];
if (t < minx) minx = t;
}
dp[i][j][k][l][p] = minx;//循环存入数据
}
cout << dp[good[1][3]][good[2][3]][good[3][3]][good[4][3]][good[5][3]] << endl;//输出五维度数组
system("pause");
return 0;
}
