主题：假设你是小偷，有总重量m(m1000 )的背包。 现有的n(n32 )项目。
总量分别为W1、W2、Wn。 而且，物品有价值，分别是V1、V2、Vn。 m、n、wi(1=I=n )都是正整数，
而且，每个项目的数量不受限制。 也就是说，可以重复得到一个项目。 寻求可佩戴的最大总价值。
输入格式：
第一行是两个正整数m和n
其次，n行分别是n对整数，分别表示该物品的重量和价值。
Example:
Input:
4 3
1 1500
3 2000
4 3000
Output :
6000
【分析】1 .状态显示
dp[i][j]表示前I件物品进入容量为j的背包的最大价值。
2 .状态转移方程：
dp[i][j]=dp[i-1][j]，jw[i]，即背包中不能放入第I个
DP[I][j]=max(DP[I-1][j]，dp[i][j-W[i]] V[i] )，j=W[i]，即背包中可以放入第I个物品。 浏览装下后是否价值更高，稍后举例说明。
3 .边界条件
dp[i][0]=0，dp[0][j]=0
第DPI个物品(背包重量j 0123400000001 (1，1500 ) 015003000450060002 (3，2000 ) 01500300045006000 ) 4， 3000 ) 01500300045006000例，01500000 0=j=2，j为3时，可以放物品2，dp[1][3]为4500，DP [1] [3-2] v [ I ]=15000
代码：//project : DP _ full back date 33602019/01/11 author : frankyu主题：假设您是小偷，您有一个总重量为m(m1000 )的背包。 现有的n(n32 )项目。 总量分别为W1、W2、Wn。 而且，物品有价值，分别是V1、V2、Vn。 m、n、wi(1=I=n )都是正整数，而且每个项目的数量没有限制，可以重复拥有一个项目。 寻求可佩戴的最大总价值。 输入格式：第一行是两个正整数m和n接下来的n行分别是n对整数，分别表示该物品的重量和价值。 example : input :43115003200043000 output:6000【分析】1 .状态显示dp[i][j]显示前I个物品的容纳容量为j的背包的最大价值。 2 .状态转移方程： dp[i][j]=dp[i-1][j]，jw[i]，即背包上第I个物品dp[i][j]=max(dp[i-1][j] )， 无法安装jw[i]的安装后价值是否更高3 .边界条件DP [ I ] [ j ]=0*/# include cstdio # includecstdlib # include cstring # include cmath # include include iterator # include algorithm # include iostream # define maxm 1000 # define maxn 32 usingnamespacestd； int W[maxn]，V[maxn]； //表voiddisplay(intDP[maxn][maxm]，int n，int m ) {for ) intI=0； i=n； I ) for(intj=0； j=m； j({coutDP[I][j] '； }cout endl； (//主函数int main ) ) {int m，n； int dp[maxn][maxm]； scanf('%d '，m )； //背包重量Scanf('%d '，n )； //物品的种类for(intI=0； i=n； I ) for(intj=0； j=m； j ) dp[i][j]=0； for(intI=1； i=n； (I )//下标是第几个，W[0]一直是0 ) scanf )、W[i]； scanf('%d '，V[i] )； //填写表格for(intI=1； i=n； I ) for(intj=1； j=m； j ) if(jw[I] ) {dp[i][j]=dp[i - 1][j]； }else{DP[I][j]=max(DP[I-1][j]，DP[I][j-w[I] ) v[I] )； }显示(DP，n，m )； cout dp[n][m] endl； 返回0； 结果截图：
下面的示例读者可以自己写一张表，试着用手计算并执行代码。 结果可以看到下一篇。 动态规划-完全背包优化
输入
6 3
2 3
4 7
3 6
输出功率
12
更多数据结构和算法实现：数据结构(严蔚敏版)和算法实现(包括所有代码)。
如果有问题的话请在下面评论。 转载请注明出处，并附上原文链接。 谢谢你。 如有侵权，请及时联系。