算法c++实验分析 1、<验证> 输入背包容量，物品数量、价值及重量，利用动态规划法解决0-1背包问题，要求输出装入物品的对应指示向量，并分析该算法性能。 2、<探索> 当背包允许物品部分装入时，重新设计动态规划策略，满足背包承载最大时价值最高，输出指示向量，并与问题1结果相比较，同时分析算法性能差异。

对于问题1，动态规划解决0-1背包问题的时间复杂度为O(nW)，其中n为物品数量，W为背包容量。具体实现过程中，可以使用一个二维数组dp[i][j]表示在前i件物品中选择一些物品放入容量为j的背包中所能获得的最大价值。根据动态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，可以求解出最大价值。最后倒序遍历dp数组确定放入背包的物品。

对于问题2，可以将0-1背包问题转换成部分背包问题。具体实现过程中，可以使用一个一维数组dp[j]表示在容量为j的背包中所能获得的最大价值。根据动态转移方程dp[j] = max(dp[j], dp[j-w[i]]+v[i])，可以求解出最大价值。同时，记录下放入背包的物品数量和对应的价值，即可输出指示向量。

相比于问题1，问题2的时间复杂度为O(nW)，空间复杂度为O(W)。可以看出，问题2在时间和空间上都优于问题1。