这里有一堆物资待分配，物资总数量不超过200（
），每件物资重量不超过100（
）。
请问是否可以将这堆物资分配给两个队伍，使得两个队伍的全部的物资重量和相等。
[编程题]两只队伍分物资
其实就是0-1背包问题
class Solution: def canPartition(self , nums): # write code here if nums == []: return True if sum(nums) % 2 == 1: return False target = int(sum(nums) / 2) dp = [True] + [False] * target for i, num in enumerate(nums): for j in range(target, num - 1, -1): dp[j] |= dp[j - num] return dp[target]
发表于 2021-01-15 11:05:02
回复(1)
class Solution:
def canPartition(self , nums):
# write code here
if nums == []:
return True
if sum(nums) % 2 == 1:
return False
target = int(sum(nums) / 2)
dp = [True] + [False] * target
for i, num in enumerate(nums):
for j in range(target, num - 1, -1):
dp[j] |= dp[j - num]
return dp[target]
def canPartition(self , nums):
# write code here
if nums == []:
return True
if sum(nums) % 2 == 1:
return False
target = int(sum(nums) / 2)
dp = [True] + [False] * target
for i, num in enumerate(nums):
for j in range(target, num - 1, -1):
dp[j] |= dp[j - num]
return dp[target]
发表于 2021-01-15 16:10:47
回复(0)
就是一个0-1背包的变形，我们首先考虑能不能对半分，不能直接返回，如果能，那么我们就类似的把背包的空间看成sum/2，每一个物品的重量既是重量也是需要的空间，我们最后只需要看能不能装满sum/2即可。
class Solution {
public:
/**
*
* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @return bool布尔型
*/
int dp[10000000];
bool canPartition(int* nums, int numsLen) {
int sum=0;
for(int i=0;i<numsLen;i++)
sum+=nums[i];
if(sum%2!=0)
return false;
else
{
sum/=2;
for(int i=0;i<numsLen;i++)
for(int j=sum;j>=nums[i];j--)
{
//if(j-nums[i]>=0)
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
if(sum==dp[sum])
return true;
else
return false;
}
//return true;
}
};
发表于 2021-03-12 21:59:23
回复(0)
发表于 2023-11-03 09:13:01
回复(0)
# 回溯法问题
class Solution:
def canPartition(self , nums):
# write code here
if not nums:
return True
sums = sum(nums)
if sums % 2 != 0:
return False
if max(nums) > sums:
return False
average = sums/2
count = 0
total = 0
vis = set()
def dfs(count,total):
if total == average:
total = 0
count += 1
if count == 2 and total == 0 and len(vis) == len(nums):
return True
for i in range(len(nums)):
if i and nums[i] == nums[i-1] and i-1 not in vis:
continue
if nums[i]+total<=average and i not in vis:
vis.add(i)
if dfs(count,total+nums[i]):
return True
vis.remove(i)
return False
return dfs(count,total)
class Solution:
def canPartition(self , nums):
# write code here
if not nums:
return True
sums = sum(nums)
if sums % 2 != 0:
return False
if max(nums) > sums:
return False
average = sums/2
count = 0
total = 0
vis = set()
def dfs(count,total):
if total == average:
total = 0
count += 1
if count == 2 and total == 0 and len(vis) == len(nums):
return True
for i in range(len(nums)):
if i and nums[i] == nums[i-1] and i-1 not in vis:
continue
if nums[i]+total<=average and i not in vis:
vis.add(i)
if dfs(count,total+nums[i]):
return True
vis.remove(i)
return False
return dfs(count,total)
发表于 2021-07-21 20:54:50
回复(0)
class Solution {
public:
/**
*
* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @return bool布尔型
*/
int sum(int* nums,int numsLen){
int sum_=0;
for(int i=0;i<numsLen;i++){
sum_+=nums[i];
}
return sum_;
}
/**
*
* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @return bool布尔型
*/
bool canPartition(int* nums, int numsLen ) {
// write code here
int sums=sum(nums,numsLen);
//printf("%d %d",sums,numsLen);
if(numsLen<2) return 0;
if(sums%2==1) return 0;
int target=sums/2;
bool dp[target+1];
dp[0]=true;
for(int i=1;i<target+1;i++){
dp[i]=false;
}
for(int i=0;i<numsLen && !dp[target];i++){
if(nums[i]<=target){
for(int j=target;j>=0;j--){
if(dp[j]&&j+nums[i]<=target){
dp[j+nums[i]]=1;
}
}
}
}
return dp[target];
}
};
发表于 2021-02-06 23:26:23
回复(0)
问题信息
通过挑战的用户
-
2022-11-01 18:13:55 -
2022-11-01 17:54:43
-
2022-11-01 16:11:17 -
2022-11-01 15:40:38 -
2022-11-01 10:46:33
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
