问题描述：
一个小偷去偷金库（这个小偷比较NB~），带了一个能承重N的背包，金库里放了不同品质的金砖，以（重量，价值）形式给出，问小偷怎样拿，获利最大？
输入：
第一行：金砖数目， 背包承重能力；
其他行：金砖重量， 金砖价值
输出：
带走金砖数目；带走最大价值；金砖序号
input：
3 50
10 60
20 100
30 120
output:
2
220
2 3
这道题是典型的动态规划，跟公正陪审团问题的解法相似：
利用
f[j][k]：j=带走金砖数目，k=金砖重量，f[j][k]：带走金砖数目=j，且金砖重量=k时的价值；
分几层循环，
最外层遍历所有的数量j：[0,n)
第二层遍历所有可能的重量：k:[0,M] 判断f[j][k]>=0来决定是否进入循环（根据j 来判断，根据j 计算j+1）
内层遍历所有的金砖i：[1,n]
if( f[j][k]+v[i] > f[j+1][k+w[i]]&&k+w[i]<=M)
{
检测i是否出现过，若没有出现过 f[j+1][k+w[i]] = f[j][k]+v[i];
（初始条件是f[0][0]=0;
）
}
#include
#include
#include
#include
#include using namespace std;
int f[30][1000];
int Path[30][1000];
int w[300];
//质量;
int v[300];
//价值;
set index;
//存放最终方案int main()
{
int i,j,k;
int t1,t2;
int n,M;
//n为数量，m为最大重量;
while(scanf("%d %d",&n,&M))
{
if(n==0&&M==0)break;
for(i=1;
i<=n;
i++)
scanf("%d %d",&w[i],&v[i]);
memset(f,-1,sizeof(f));
memset(Path,0,sizeof(Path));
f[0][0]=0;
//初始化条件，根据f[0][0]推以后的结果for(j=0;
j=0)//方案f[j,k]可行，从f[0][0]开始;
{
for(i=1;
i<=n;
i++)
if( f[j][k]+v[i] > f[j+1][k+w[i]]&&k+w[i]<=M) //若f[j+1][k+w[i]]已经有值，则保存较大的一个;
{
t1=j;
t2=k;
while(t1>0&&Path[t1][t2]!=i)//验证i是否在前面出现过;
{
t2-=w[Path[t1][t2]];
//减前一个元素的重量;
t1--;
}
if(t1==0)//若i未出现过;
{
f[j+1][k+w[i]] = f[j][k]+v[i];
Path[j+1][k+w[i]]=i;
}
}
}
}int maxNum=0,maxV=0,maxW=0;
for (int i=1;
i<=n;
i++)
{
for (int j=0;
j<=M;
j++)//注意必须 =M
{
if(maxV::iterator iter=index.begin();
iter!=index.end();
iter++) cout<<*iter<<" ";
}
return 0;
} 0-1背包问题和陪审团问题都是属于动态规划中的同一类问题，这种问题比较难做（我比较菜鸟，这是我的感觉啊~）
这类问题关键要换个思路，要给最优解添加约束条件：f[j][k],k金砖重量就是约束条件，要根据约束条件k进行迭代k[0,M]，迭代的过程要首先判断是否符合题意：if(f[j][k]>=0)，
最内层要不断的组合没有计算过的元素，根据已知推未知f[j+1][k+w[i]] = f[j][k]+v[i];
另外部分背包问题可以用贪心算法解决（相当于小偷偷的是金沙）背包问题还有很多种，这都以后再讲。
【动态规划|每日一题(7)——0-1背包问题(动态规划)】续……
读完背包九讲发现我解题的方法略复杂，其实利用一维数组就可以实现动态规划，
根据状态转移方程：f[w]=max{f[w], f[w-c]+v}
f[w]表示在重量为w时的最优解，
参考网上一位大牛重新写的代码：
#include using namespace std;
const int nMax=400;
//待选物品数;
const int mMax=10000;
//最大载重;
struct{
int wei,val;
}node[nMax];
int main()
{
int m, n, i ,w ,dp[mMax];
while(cin>>n>>m)//n为待选物品数量，m为最大载重量;
{
if(m==0&&n==0) break;
for (i=1;
i<=n;
i++)
cin>>node[i].wei>>node[i].val;
memset(dp, 0, (m+1)*sizeof(int));
for (i=1;
i<=n;
i++)
for ( w=m;
w>=node[i].wei;
w-- )
if ( dp[w] < dp[w - node[i].wei] + node[i].val )
dp[w] = dp[w - node[i].wei] + node[i].val;
cout< DynamicProgram问题也真是博大精深呐~ 题在精而不在多~
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络